백준 2589 보물섬 파이썬 문제풀이 (python DFS BFS)

문제 보러가기

 

백준 보물섬 파이썬 문제풀이

보물섬은 L(land) 육지와 W(water) 바다 중 육지만을 한 번씩만 밟으며 

상하좌우로 갈 수 있는 곳 중 가장 서로 멀리있는 보물을 찾는 문제이다.

 

즉 L로 되어있는 칸 중 서로 가장 멀리 떨어져있는 칸이 얼마나 거리를 두고 있는지를 

구하면 되는 문제이다.

 

BFS를 이용해서 풀려고 하는데 모든 L칸마다 탐색을 해보아야한다.

 

정답코드

from collections import deque

v,h = map(int,input().split())
treasure = [list(input().strip()) for _ in range(v)]
maxLength = 0

for i in range(v):
    for j in range(h):
        if treasure[i][j] == 'L':
            visited = [[0 for _ in range(h)] for _ in range(v)]
            dist = [[0 for _ in range(h)] for _ in range(v)]

            # BFS
            q = deque()
            q.append([i,j])
            visited[i][j] = 1

            while q:
                ey,ex = q.popleft()
                # 4방향 탐색
                for dy, dx in [[0,1], [1,0], [-1,0], [0,-1]]:
                    ny, nx = ey + dy, ex + dx
                    if 0 <= ny < v and 0 <= nx < h:
                        if treasure[ny][nx] == 'L':
                            if visited[ny][nx] == 0:
                                visited[ny][nx] = 1
                                dist[ny][nx] = dist[ey][ex] + 1
                                maxLength = max(maxLength, dist[ny][nx])
                                q.append([ny,nx])
print(maxLength)

문제는 생각보다 난해하다.

보물지도를 입력으로 받으면, 각 보물지도의 순회하면서 L칸인 경우 로직이 시작된다.

 

visit 배열과 dist 배열을 초기화하고, BFS를 위한 queue를 만들어서

4방향 BFS탐색을 진행한다.

 

그리고 방문하지 않은 visit == 0 으로 이동할 때마다 

방문 표시 및 dist를 전 칸에서 1씩 증가하여 표기한다.

또 dist를 기록하면서 max length도 업데이트 하는 과정을 BFS에 포함한다.

 

이렇게 모두 탐색하면서 가장 먼 거리를 maxLength에 저장하는 방식이다. 

 

맞았다. 하지만 빠른 시간 안에 코드를 짤 수 있으면 한다.