[파이썬] 백준 2589 : 보물섬 (골드5)

[파이썬] 백준 2589 : 보물섬 (골드5)

 

2589번: 보물섬

---

문제

---

풀이

0. 방향성 생각

최장거리 문제라 BFS로 방향성을 잡는다.

하지만 군집 내에 점마다 거리가 달라지므로 최장거리를 찾으려면 모든 점을 탐색해야한다. (더 좋은 방법은 모르겠다)

 

1. 입력 받기

from collections import deque
import sys
input = sys.stdin.readline

h,w = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(input()))

arr에 입력을 받는다.

2. BFS 함수 정의

def bfs(x,y):
    q = deque()
    q.append((x,y))
    visit[y][x] = 0
    d = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            if 0<=nx<w and 0<=ny<h :
                if arr[ny][nx]=='L' and visit[ny][nx]== -1 :
                    visit[ny][nx] = visit[y][x] + 1
                    q.append((nx,ny))
                    if d < visit[ny][nx] :
                        d = visit[ny][nx]
    return d

1.  큐에다가 현재 좌표를 추가하고 탐색을 시작할 위치를 0으로 초기화한다.
2. 가장 먼 거리를 받을 d를 정의한다
3. 4가지 방향을 정의해주고 범위내에 들어왔을 때 탐색하지 않은 좌표이면 탐색한 후 큐에 추가한다.
4. 탐색한 좌표에서 d값을 갱신해준다

3. 탐색 후 출력

max_d = 0
visit = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if arr[i][j] == 'L' and visit[i][j] == -1 :
            temp = bfs(j,i)
            visit = [[-1]*w for i in range(h)]
            if max_d < temp :
                max_d = temp
            
print(max_d)

1. 정답을 넣어줄 max_d를 정의한다.
2. visit을 -1로 초기화해주고 for문을 돌 때 마다 초기화해준다.
3. bfs를 실행한 결과가 max_d 보다 크면 할당해준다.

---

전체코드

from collections import deque
import sys
input = sys.stdin.readline

h,w = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(input()))
    
step = [[1,-1,0,0],[0,0,1,-1]]
def bfs(x,y):
    q = deque()
    q.append((x,y))
    visit[y][x] = 0
    d = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            if 0<=nx<w and 0<=ny<h :
                if arr[ny][nx]=='L' and visit[ny][nx]== -1 :
                    visit[ny][nx] = visit[y][x] + 1
                    q.append((nx,ny))
                    if d < visit[ny][nx] :
                        d = visit[ny][nx]
    return d

max_d = 0
visit = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if arr[i][j] == 'L' and visit[i][j] == -1 :
            temp = bfs(j,i)
            visit = [[-1]*w for i in range(h)]
            if max_d < temp :
                max_d = temp
            
print(max_d)

python3는 55%에서 시간초과해서 pypy3로 풀었다.

어찌보면 시간초과가 당연한거라 나중에 더 좋은 방법 있으면 다시 풀어보기로