JJ_blog

문제를 해결하는 아이디어는 가장 넓은 안전 영역을 구하는 것이므로 벽을 설치한 후 바이러스를 퍼트려보고 완료된 그래프를 탐색하여 안전영역의 개수를 출력하면 되는 문제이다. 바이러스를 퍼트리고 안전영역을 찾는건 정말 쉬운 문제인데.. 이놈의 벽..! 해당 문제를 처음 딱 읽고 이해는 갔지만 이 벽이 문제였다. 벽 3개를 어떻게 배치를 할 것인가.. 처음에 반복문을 이용하여 배치를 해보았지만 내 구현 능력이 부족한지 계속해서 실패하였다. ㅜㅜ 결국.. 인터넷의 힘을 빌릴 수 밖에..ㅠ 재귀를 이용하여 벽을 세우는데 약간 신기했다. (새로운 패턴 익히는 중) □ 소스코드 #include using namespace std; vector inputOrginal14502(9,vector(9,0)); vector ..

솔직히 처음 문제를 읽었을 때 N이 비가 내리는 양을 포함하는 줄 알고 풀었다. 신기하게 문제에서 제공해 주는 예제들이 모두 통과가 되었다 ㅋㅋㅋ 그리고 제출했더니.; 틀렸습니다 (눈물..) 문제를 조금 꼼꼼하게 읽어보니 안전영역이 덩어리 지는 최대의 개수를 구하는 것이었다...!! 바로 수정.. 어렵지 않고 쉬운 문제였다. □ 소스코드 #include using namespace std; vector input2468(101,vector(101,0)); vector check2468(101,vector(101,false)); int count2468 = 0; int rain2468 = 0; queue q2468; void bfs2468(int N,int x, int y){ int dx[] = {0,0,..

대각선이 포함하여 덩어리 개수를 세면 되는 문제이다. 상하좌우 덩어리를 세는 문제에서 활동 범위를 대각선으로만 늘리면 해결 할 수 있다. □ bfs 버전 #include using namespace std; vector input4963(51,vector(51,0)); vector check4963(51,vector(51,false)); queue q4963; void bfsIsland4963(int N, int M, int x, int y){ int dx[] = {0,0,1,-1,1,-1,1,-1}; int dy[] = {1,-1,0,0,1,1,-1,-1}; while (!q4963.empty()) { int frontX = q4963.front().first; int frontY = q4963.fro..

약간 새로운 패턴의 문제였다. 그냥 약간의 노가다(?) 문제 일반인의 덩어리를 세는 부분은 R,G,B를 모두 나누어 개수를 세면 되지만 적록색약의 덩어리를 세는 부분은 (R,G), B를 나누어 개수를 세면 끝이다 쉽죠? □ 소스코드 #include using namespace std; vector input10026(101,vector(101,0)); vector check10026(101,vector(101,false)); vector checkNotRG10026(101,vector(101,false)); bool dfsBlue10026(int N, int x, int y){ if(xN) return false; if(input10026[x][y] == 'B' && !check10026[x][y] ){..

해당 문제는 1차원 배열을 이용하여 해결할 수 있는 문제이다. dfs로 구현하였고, 헷갈리지만 않는다면 쉽게 풀 수 있다. □ 소스코드 #include using namespace std; vector input11724[1001]; vector check11724(1001,false); void dfs11724(int x){ check11724[x] = true; for(int i=0;i>N>>M; for(int i=0;i>a>>b; input11724[a].push_back(b); input11724[b].push_back(a); } int result = 0; for(int i=1;i

BFS를 이용하여 해결하는 문제인 것은 알고 있었지만 그냥 최단 거리가 아닌 벽을 하나 부순다는 상황이 주어져서 더욱더 혼란스러워졌다. 2일 동안 생각을 해보고 도전을 해봤지만 실패... 혼자서는 도저히 못 풀겠다는 생각이 들어 인터넷 블로그의 힘을 살짝 빌렸다..ㅠ 다른 사람들이 해결했던 방법들을 보고 이해한 후 문제를 보고 다시 풀었다..... 해결 방법 최단 거리를 측정하는 패턴은 기존 벽을 부수지 않고 이동하는 것과 동일하다. 하지만 최단거리로 가기 위해 벽을 한번 부수려면 모든 벽을 탐지한 후 벽을 부숴야 한다. 출발하자마자 벽을 부수고 가는 것이 최단 거리일 수 있지만 도착지가 벽으로 둘러 싸여 있는 경우 벽 부수는 스킬을 아껴 놓아야 한다. 해당 사례가 아래 그림이다. 출발지 0(a) 0(b..

BFS를 이용하여 문제에 적힌 규칙을 적용했다. 처음 풀었을 때는 사다리를 만나면 타고 뱀을 타면 무시하는 방법으로 풀었더니 계속 틀렸다. 반례 세 번째 같은 경우가 있어서 뱀을 타고 가는 경우가 있다. 그 외에는 어려운 부분 없이 쉽게 풀 수 있다. #include int slgN, slgM; struct slgMv{ int y; bool visitied; }typedef slgMV; slgMV slgList[101] = {0}; int slgTotalTime = 0; void slgBFS(){ queue slgQ; slgQ.push({1,1}); int dx[] = {1,2,3,4,5,6}; while(!slgQ.empty()){ int x = slgQ.front().first; int time = ..

7576번 토마토는 2차원 문제였다면 이번에는 3차원으로 해결하는 문제이다. 2차원 문제를 쉽게 풀었다면 3차원이라고 딱히 막 어렵지 않았다. 2차원 문제와 다른 게 배열범위랑 탐색하는 범위가 살짝 늘어났지만 조금만 생각하면 쉽게 해결할 수 있다. #include #define MAXSIZE 101 int toM3,toN3,toH3; int inBoxSizeV3[MAXSIZE][MAXSIZE][MAXSIZE]; //면, 행, 열 순서 queue tomatoQV3; //면, 행, 열 순서 int tomatoMaxTimeV3 = 0; void toBFSV3(){ int dX[] = {1,-1,0,0,0,0}; int dY[] = {0,0,1,-1,0,0}; int dZ[] = {0,0,0,0,1,-1}; w..

처음에 접근을 DFS를 이용하여 토마토 집단이 몇 개인지 알아보고 최소일을 구하는 방식으로 접근했는데 BFS에 대한 이해가 부족했던 것 같다. BFS는 queue에 넣고 반복문을 통해 계산을 진행해서 출발 점이 여러 개여도 큐 안에 미리 넣기만 하면 여러 출발점에서도 동작시킬 수 있다. #include #define MAXBOXLENGTH 1001 int toM,toN; int inBoxSize[MAXBOXLENGTH][MAXBOXLENGTH]; queue tomatoQ; int tomatoMaxTime = 0; void printResult(); void toBFS(){ int dX[4] = {1,-1,0,0}; int dY[4] = {0,0,1,-1}; while(!tomatoQ.empty()){ i..

별다른 문제없이 해결했지만.. 초기화를 할 때 범위를 300이 아닌 301로 지정하여 수십 번 틀렸다..ㅠ 이차원상의 이동을 하는 문제는 이동가능한 범위를 배열로 나타내어 문제를 풀면 쉽게 풀 수 있다. 최단 거리를 찾는 문제들은 bfs를 사용하면 문제를 해결할 수 있는 것 같다. #include int testCase; int length; int finalX, finalY; //최종 도착지 int mvCount; bool knightVisited[301][301] = {false}; int knightCount[301][301]; void printLocate(); void printVisited(); void knightBFS(int x,int y){ queue knightQ; knightQ.pus..