[BOJ] 백준 11403번 - 경로 찾기(with Java)

알고리즘

다른 문제들과는 다르게 입력이 인접리스트가 아닌 인접행렬로 주어지는데, 필자는 인접행렬보다 인접리스트로 문제를 푸는 방식이 더 익숙해서 인접행렬을 입력받은 후에 인접리스트로 바꿔주었다. 여태까지 만나본 그래프 문제들은 모두 방향성이 없는 무방향 그래프였는데, 이 문제의 경우에는 방향 그래프를 사용하여 경로를 구하도록 했기 때문에 어렵게 느껴졌다. 아래에 인접리스트와 그래프를 도식화시킨 그림을 나타내보았다.

 

입력받은 인접행렬을 인접리스트로 바꿔주면 각각의 정점들에 대해서 DFS 알고리즘을 적용하면 된다. 일반적인 DFS 알고리즘은 현재 정점에 대해서 방문했음을 표시해주고, 인접한 정점들에 대해서 방문 여부에 따라 DFS 알고리즘을 재귀적으로 수행한다. 하지만 이 문제는 정점 i가 정점 i에 도착한다는 보장이 없으므로 인접한 정점이 방문되지 않았다면 해당 정점에 대해서 DFS 알고리즘을 적용하기 전에 그 정점이 방문됐음을 표시해주기로 한다.

 

하나의 정점에 대해서 경로 찾기가 끝나게 되면, visited 배열 전체에 대해서 true로 바뀐 정점들만 추출하여 입력받은 인접행렬의 값을 0에서 1로 갱신해주면 된다. 또한, visited 배열을 재사용해주기 위해서 true로 바뀐 값들을 전부 false로 바꿔주면 다음 정점에서 다시 경로 찾기가 시작된다.

소스코드

문제링크

11403번: 경로 찾기