문제 링크:https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net BFS, 완전탐색 각각의 육지에 대해서 BFS로 다른 육지까지 최단거리를 모두 구하고, 최단거리 중에서 최장거리를 찾으면 됩니다. 가로, 세로의 크기는 최대 50 이하입니다. 임의의 한 정점에서 다른 모든 정점까지 BFS로 최단 거리를 구하면 O(N*M)의 시간복잡도를 가지고, 최대 정점의 개수는 N*M이므로 전체 시간 복잡도는 O((N*M)^2)의 시간복잡도가 됩니다. 따라서 주어진 시간..

문제 링크: https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS, 최단거리 이문제는 모든 물에 대해서(물을 모두 큐에 담으면 됨) BFS로 물에서 모든 정점까지의 최단 거리를 구하고, 고슴 도치에 대해서 똑같이 BFS를 진행하면서 물 보다 더 최단 거리로 이동할 수 있는 경우만 큐에 담으면 됩니다. 주의할 점은 입력으로 물이 없을 수도 있습니다(물이 없으면 물의 visited 최단 거리 배열 값은 -1). 1 2 3 4 5 6 7 8 9 10 11 12..