🟩 [백준] [Python] 2589번_보물 탐색

문제

https://www.acmicpc.net/problem/2589

2589번: 보물섬

풀이

Python3 에서 사용한 풀이

# 백준 2589번 문제 -보물 탐색
from collections import deque
n, m = map(int, input().split())
dx, dy = [0,0,-1,1], [1,-1,0,0]
graph = [list(map(str, input())) for _ in range(n)]
def bfs(x,y):
    q = deque()
    q.append((x, y))
    cnt = 0
    visited = [[0]*m for _ in range(n)]
    visited[x][y] = 1
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and graph[nx][ny] == 'L':
                visited[nx][ny] = visited[x][y] + 1
                cnt = max(cnt, visited[nx][ny])
                q.append((nx, ny))
    return cnt - 1
result = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'L':
            # 가장자리가 아님
            if i>0 and i+1<n:
                if graph[i-1][j] == "L" and graph[i+1][j] == "L":
                    continue
            if j>0 and j+1<m:
                if graph[i][j-1] == "L" and graph[i][j+1] == "L":
                    continue
            result = max(result, bfs(i,j))
print(result)

이 풀이는 백트래킹과 BFS를 사용하여 문제를 풀어주었다.

처음에는 백트래킹을 사용하지 않아서 pypy3에서만 통과가 되었다.

L을 탐색할 때 가장자리 인지 확인해주는 코드를 추가 하였는데 300ms 차이가 났다. 

# 가장자리가 아님
            if i>0 and i+1<n:
                if graph[i-1][j] == "L" and graph[i+1][j] == "L":
                    continue
            if j>0 and j+1<m:
                if graph[i][j-1] == "L" and graph[i][j+1] == "L":
                    continue

이러한 세세한 부분들을 잘 파악해야 코딩테스트를 잘 하게 되는 것 같다.