[파이썬]백준 2589 보물섬

링크

백준 2589 보물섬

처음엔 어떤 곳이든 시작만 해서 가장 끝의 좌표를 찾은 다음 해당좌표부터 bfs를 다시돌려서 길이를 계산하면 구할 수 있을 것이라 생각했으나 내가 생각하지 못한 반례가 있는지 틀렸다.

그 후 완전탐색을 하게끔 코드를 짰더니 파이썬으론 시간초과가 났으나 Pypy로는 통과됐다.

이후 스터디를 통해 알게된 사실은 파이썬으로 통과하기 위해선 delta를 반복하는 것이 아니라 delta를 if문으로 분기시켜서 하나하나 따져서 조건으로 구현하면 통과가 된다는 것을 알았으나..
너무 노가다라서 이문제는 Pypy로 푼것으로 만족!

오답 1

가장 끝 좌표를 찾은 후 해당 좌표부터 다시 bfs탐색하는 전략 -> 실ㅋ패ㅋㅋ

from collections import deque

def bfs(i, j):
    global max
    sr, sc = i, j
    q = deque()
    q.append((i, j))
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < H and 0 <= nc < W:
                if t_map[nr][nc] == 'L' and dis[nr][nc] == -1:
                    dis[nr][nc] = dis[r][c] + 1
                    q.append((nr, nc))
                    if dis[nr][nc] > max:
                        max = dis[nr][nc]
                        sr, sc = nr, nc
    return sr, sc


H, W = map(int, input().split())
t_map = [input() for _ in range(H)]
dis = [([-1] * W) for _ in range(H)]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
start = deque() #구역별 끝지점
max = 0

for i in range(H):
    for j in range(W):
        if t_map[i][j] == 'L' and dis[i][j] == -1:
            dis[i][j] = 0
            sr, sc = bfs(i, j)
            start.append((sr, sc))

dis = [([-1] * W) for _ in range(H)]
max = 0
while start:
    i, j = start.popleft()
    dis[i][j] = 0
    bfs(i, j)

print(max)

정답 코드

from collections import deque
from copy import deepcopy

def bfs(i, j):
    max = 0
    q = deque()
    q.append((i, j))
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < H and 0 <= nc < W:
                if t_map[nr][nc] == 'L' and dis[nr][nc] == -1:
                    dis[nr][nc] = dis[r][c] + 1
                    q.append((nr, nc))
                    if dis[nr][nc] > max:
                        max = dis[nr][nc]
    return max


H, W = map(int, input().split())
t_map = [input() for _ in range(H)]
original = [([-1] * W) for _ in range(H)]
dis = deepcopy(original)
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
ans = 0

for i in range(H):
    for j in range(W):
        if t_map[i][j] == 'L':
            dis[i][j] = 0
            tmp = bfs(i, j)
            if tmp > ans:
                ans = tmp
            dis = deepcopy(original)

print(ans)

알게된 것👨‍💻

• 효율적으로 짜보겠다고 하다가 틀린 답을 내느니 일단 완전탐색으로 해보자 그 후에 다시 효율적으로 짜보자!