문제

문제 링크

---

풀이

초기 아이디어 및 문제점

간단히 bfs로 풀 수 있는 문제라고 생각했다. 어떤 두 점 사이의 거리가 최대가 되는 지점에 보물이 있고 그럴 때의 최대 거리(여기서는 시간으로 표현)를 출력하면 되는 문제였다. 즉 모든 점에 대해서 해당 점을 시작점으로 하는 bfs를 수행하고 graph의 최댓값을 뽑아내면 된다고 생각했다.

'W'를 -1로, 'L'을 0으로 변환한 후 bfs를 수행하기로 했다.

from collections import deque
import copy

def bfs(graph, start, dx, dy):
    graph = copy.deepcopy(graph)
    q = deque([start])
    graph[start[1]][start[1]] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < hor and 0 <= ny < ver and graph[ny][nx] == 0:
                graph[ny][nx] = graph[y][x] + 1
                q.append((nx, ny))
        
    return max([max(row) for row in graph]) - 1
        
ver, hor = map(int, input().split())
graph = []
for _ in range(ver):
    graph.append(list(map(lambda x: 0 if x == 'L' else -1, list(input()))))

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

dists = [bfs(graph, (x, y), dx, dy) for y in range(ver) for x in range(hor) if graph[y][x] == 0]

print(max(dists))

하지만 간과한 부분이 하나 있었다.
해당 코드는 모든 'L'을 0으로 변환한다. 즉 어떤 점을 시작점으로 삼았을 때 시작점 또한 0으로 시작한다.
graph[0][0]이 시작점이고 graph[1][0]이 'L'이라고 가정해보자.
graph[1][0]의 값은 1로 변하고 q에는 (0, 1)이 들어간다.
이 때 시작점의 값은 그대로 0이므로 시작점을 한번 더 탐색하게 된다.
이는 최단거리를 찾는데에 방해가 되고 문제 조건에도 위배되므로 올바른 동작이 아니다. 틀린 결과를 만들어낼 수 있다.

정답 코드

해결법은 시작점의 값을 1로 초기화하는 것이다. 이 경우 거리를 나타낼 그래프 각 점의 값이 1씩 증가하게 되므로 bfs의 반환값에서 1을 빼주면 된다.

from collections import deque
import copy

def bfs(graph, start, dx, dy):
    graph = copy.deepcopy(graph)
    q = deque([start])
    graph[start[1]][start[0]] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < hor and 0 <= ny < ver and graph[ny][nx] == 0:
                graph[ny][nx] = graph[y][x] + 1
                q.append((nx, ny))
        
    return max([max(row) for row in graph]) - 1
        
ver, hor = map(int, input().split())
graph = []
for _ in range(ver):
    graph.append(list(map(lambda x: 0 if x == 'L' else -1, list(input()))))

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

dists = [bfs(graph, (x, y), dx, dy) for y in range(ver) for x in range(hor) if graph[y][x] == 0]

print(max(dists))

---

후기

반례를 생각하는 것이 참 중요하면서도 어렵다.