Floyd-Warshall2 [BOJ] 백준 9205번 - 맥주 마시면서 걸어가기(with Java) 알고리즘 아이디어를 떠올릴 수 있다면, Floyd-Warshall 알고리즘을 이용해서 간단하게 BFS로 풀 수 있는 문제이다. 설계를 잘했다면 문제를 푸는 방법은 매우 간단하다. 우선, 각각의 위치를 정의해줘야만 하는데 좌표가 음수가 될 수도 있으므로 배열을 이용한 풀이는 어렵다. 따라서 현재 위치 x, y 좌표와 해당 위치의 방문 여부 정보 및 시작점과의 거리 정보를 담고 있는 클래스를 만들어준다. 또한, 모든 편의점과 목적지는 시작점과의 거리 정보를 무한대로 설정해주고 각각의 객체들을 리스트에 넣어준다. 이제부터 각각의 정점들에 대해서 BFS를 수행하면 되지만, 여기서 고려해줘야할 사항이 하나 있다. 문제에서 주어진 '맥주 한 박스에는 맥주가 20개 들어있다', '50미터를 가려면 그 직전에 맥주 한.. 2021. 12. 15. [BOJ] 백준 11403번 - 경로 찾기(with Java) 알고리즘 다른 문제들과는 다르게 입력이 인접리스트가 아닌 인접행렬로 주어지는데, 필자는 인접행렬보다 인접리스트로 문제를 푸는 방식이 더 익숙해서 인접행렬을 입력받은 후에 인접리스트로 바꿔주었다. 여태까지 만나본 그래프 문제들은 모두 방향성이 없는 무방향 그래프였는데, 이 문제의 경우에는 방향 그래프를 사용하여 경로를 구하도록 했기 때문에 어렵게 느껴졌다. 아래에 인접리스트와 그래프를 도식화시킨 그림을 나타내보았다. 입력받은 인접행렬을 인접리스트로 바꿔주면 각각의 정점들에 대해서 DFS 알고리즘을 적용하면 된다. 일반적인 DFS 알고리즘은 현재 정점에 대해서 방문했음을 표시해주고, 인접한 정점들에 대해서 방문 여부에 따라 DFS 알고리즘을 재귀적으로 수행한다. 하지만 이 문제는 정점 i가 정점 i에 도착한.. 2021. 7. 25. 이전 1 다음
