공부공간

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

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

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