공부공간

매년 주변(상 하 좌 우)의 0의 개수만큼 빙산이 녹는 문제이다. 최종적으로 DFS탐색했을때, 2덩어리 이상으로 분리되는 시점을 구하는것이다. MAP으로 입력을 받고, COPY_MAP을 선언하여 주변의 0의 개수의 정보를 담는 배열을 선언하고 DFS로 덩어리의 수를 찾으면서 두 덩어리 이상이 되는 시점을 찾는다. 매년 업데이트되는 MAP의 정보는 MAP = MAX(MAP[Y][X] - COPY_MAP[Y][X])로 0 이하가 되지않으면서 전체가 0이 되었을 때에는 두덩어리 이으로 분리되지 않으며 끝남을 의미하므로 이 경우를 체크래줄수있는 CHECKZERO 함수를 매 DFS실행시 체크해준다. 살짝 까다로울 수 있지만, COPYMAP을 이용하면 쉽게 해결할 수 있는 문제이다.

모눈 종이 위의 좌측 하단의 좌표와 우측 상단의 좌표가 주어진다. 주의해야할 점은, 이 좌표를 그대로 배열에 적용하면 모눈종이에 표시된 영역과 일치 하지 않게 된다. ex) (1,1) (2,5) 의 경우, 배열에 그대로 적용하게 된다면 2x5 의 행렬이 되어, 모눈종이 상의 1x4 의 영역과 상이하다. 따라서, 입력 받을시 배열에 적합하게 바꾸어준 후, 일반적인 방법의 DFS 알고리즘을 적용하면 어렵지 않게 해결이 가능하다. 입력 받음과 동시에, DFS 에 적용하기 쉽도록 영역의 정보를 배열로 만들어 준다. DFS 알고리즘을 통하여 영역 외의 부분을 체크하고, 영역이 총 몇 개가 있는지 도출한 뒤, 분할된 영역의 수를 저장한 벡터를 sort 함수를 통하여 오름차순으로 정렬해준 뒤 출력한다.

벽 3개를 세워 바이러스가 퍼지지 않은 안전 구역을 최대화해야 하는 문제로, BFS 및 재귀 함수의 사용이 필요하다. 문제 해결의 기본 개념은, 재귀 함수를 이용하여 0 으로 표시된 모든 부분에 대하여 벽을 세우는 것을 고려하고, BFS 를 통하여 바이러스가 퍼진 후의 데이터에서 안전영역의 수를 도출하여 지속적으로 비교하는 것이다. 기존의 입력값, 임의의 벽을 세운후의 새로운 배열, 벽을 세운 배열에서 바이러스가 퍼지고 난 다음의 배열의 총 3가지 배열이 사용되어야 한다. BFS 개념을 사용하기 위하여 큐를 선언한다. 벽이 세워진 후 복제된 배열인 replica 의 정보를 바이러스가 퍼진후의 데이터를 도출하기 위해 spread 행렬에 대입하고, queue 에 바이러스의 위치를 넣는다. 이후, BFS 의 ..

NxN 행렬의 지역 높이 데이터 정보를 입력받아, 침수된 지역을 제외한 안전 영역의 수를 DFS 를 통해 구하는 기본적인 형태의 DFS 문제이다. 침수된 지역을 제외시켜 준후, DFS 알고리즘에 지역 데이터를 넣어주면, 안전 영역을 도출할 수 있다.

DP와 DFS를 동시에 쓰는 문제이다. 2차원 배열의 모든 인덱스값을 DFS를 돌리면서 해당 인덱스에서 판다가 살아갈 날을 따로 저장해둔다. 인접한 인덱스에서 DFS로 검사해줄 때, 자기보다 큰 노드를 탐색하며 이전에 값 +1 값으로 갱신해주면서 최대한 살 수 있는 일수를 출력한다.

플로이드-워셜 알고리즘으로 해결하는 기본적 형태의 문제이다. 입력은 정점의 개수(노드의 개수) 를 의미하며, NXN의 행렬이 노드간의 연결 정보를 제공한다. 플로이드 워셜의 기본 형태인 3중 for 문을 활용하여, k = 거치는 노드, i = 시작 노드, j = 도착 노드 의 형태로 문제를 해결하고, 가중치가 없는 그래프이기 때문에 최단 거리를 갱신할 필요 또한 없다.

필요한 배추 흰지렁이의 개수를 구하는 문제이다. 인접한 배추끼리는 이동이 가능하므로 DFS를 돌면서 상하좌우의 조건을 걸어서 탐색하게 하였다. 즉 배열 전체를 돌면서, 탐색안한곳을 시작하면 배추 흰지렁이 개수를 증가시키고 그 지렁이가 갈수있는 모든 경로의 Visit 배열을 True바꾸어주었다.

문제 읽자마자 조건대로 코딩해주었다. 어떤 정수에 대해서 3으로 나누어 떨어지면서 2로나누어 떨어지는 경우 6의 배수로 처리하였고 각각 2의배수 3의 배수로 채우고, 아닌경우 x-1로 재귀호출하여서 m배열을 채워준다음에 x번째 v가 계산되면 바로 가져오는 식으로 구현하였는데, 굳이 v를 선언하지않고 m[x]>0로 이전에 계산이 되었는지 확인하면 될 것 같았다. 맞긴했지만 뭔가 찜찜한 해결.. 좀더 효율 적으로 접근해야겠다.