오늘은 백준 2589번 '보물섬' 문제에 대해 가져와봤습니다.
해당 문제는 전형적인 bfs 문제인데, 우리가 이런 BFS 문제를 풀 때 놓치면 안될 점들을 상기하면서 문제를 설명드리겠습니다.
"보물섬"문제는 주어진 지도에서 최단거리로 갈 수 있는 가장 먼 거리에 있는 두 지점을 찾는 문제입니다. 지도는 'L'(땅)과 'W'(바다)로 구성되어 있으며, 이동은 상하좌우로만 가능합니다. 이 문제의 핵심은 가장 긴 최단 거리를 찾는 것입니다.
해당 문제를 봤을 때, 뭔지 정확히는 모르셔도 '전형적인 그래프 탐색 알고리즘일 것이다' 라고 느끼셨을 겁니다.
맞습니다. 저는 이 문제를 보고 'bfs 알고리즘을 활용하면 뭔가 풀릴 것 같은데?' 라는 직감을 느꼈습니다. BFS 알고리즘을 이용하면 모든 가능한 경로를 탐색하여 최장 거리를 찾을 수 있을테니 말이죠. 그렇다면 어떤식으로 접근하면 좋을까요?
해당 문제를 BFS 로 푸는 방법은 다음과 같이 정리할 수 있겠습니다.
1. 지도 분석 : 지도에서 'L'(땅)과 'W'(바다)를 구분합니다. BFS는 'L'(땅) 지점에서만 수행됩니다.
2. 모든 'L'탐색 : 지도 상의 모든 'L' 지점에서 BFS를 시작합니다. 각 'L' 지점에서 시작하여 탐색할 때마다 최장 거리를 갱신합니다.
3. BFS 구현 : 각 'L' 지점에서 BFS를 수행하여 모든 이동 가능한 경로를 탐색합니다. 큐(queue)를 사용하여 탐색할 지점을 관리합니다.
4. 거리 계산 : 이동할 때마다 거리를 1씩 증가시켜, 최장 거리를 찾습니다.
5. 최장 거리 갱신 : 각 BFS를 실행 후, 구한 거리가 현재까지의 최장 거리보다 길다면, 최장 거리를 갱신합니다.
제가 위 생각들을 그대로 코드로 구현한 첫 코드는 아래와 같습니다.
from collections import deque
import sys
input = sys.stdin.readline
def bfs(r,c): # bfs 탐색
dist = 0 # 거리 0
dr = [-1,1,0,0]
dc = [0,0,-1,1]
visited[r][c] = True # 해당 지점 방문처리
queue = deque()
queue.append((r,c))
while queue: # queue가 빌 때까지 계속 탐색
r, c = queue.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < m and board[nr][nc] == 'L' and not visited[nr][nc]:
dist += 1
visited[nr][nc] = True
queue.append((nr,nc))
return dist
# n * m 보드 입력받기
n, m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]
answer = 0 # 최종 답
for i in range(n):
for j in range(m):
if board[i][j] == 'L': # 'L'인 지점에서
visited = [[False] * m for _ in range(n)] # visited 배열 초기화하고
answer = max(answer,bfs(i,j)) # bfs 탐색 후, 기존 answer과 비교
print(answer)
비교적 빠르게 코드를 써내려갔지만, 해당 코드에서 틀린 부분이 있습니다.
바로 dist = 0으로 초기화하고 dist를 +1 씩 증가시키는 지점이 오류입니다. 이것은 정말 최장거리를 보장할까요?
※ 'dist' 변수 사용시 문제점
- 'dist' 변수는 bfs 탐색 과정에서 전체 큐에 들어있는 노드의 수를 계산합니다. 이는 각 노드에서의 실제 거리가 아닌, 큐에서 제거된 노드의 총 수를 나타냅니다.
- BFS 는 여러 노드를 동시에 참색할 수 있기 때문에, 'dist'를 증가시키는 것은 실제로는 각 단계에서 탐색하는 노드의 수를 더하는 것과 별반 다를게 없다는 뜻입니다. 다시말해서, 이렇게 단순히 +1 을 하는 작업은 최장거리를 정확히 계산하지 못합니다.
5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW
실제로 위 예시를 적용해보면, 답은 10 이 나온다. 최단거리로 갈 수 있는 최장거리를 보장하지 않고 단순히 L로 퍼져나갈 수 있는 거리, 즉 노드의 수가 답으로 나온 셈입니다. 처음에 0으로 시작하니까 (3,0)의 L에서 시작해서 (4,1)의 L 까지 가는 거리가 10 으로 계산된 것인데, 하지만 실제로 8 로도 갈 수 있는 경로이죠.
여기서 우리가 짚고 넘어가야 할 점은 바로 최단경로를 구할 때는 따로 변수를 만들지 말고 이전 노드를 기준으로 cost를 계산해줘야 한다는 점입니다. 따로 dist 라는 변수를 만들어서 +1 을 하는식의 계산은 최단경로를 보장하지 않습니다!
개선된 코드는 아래와 같습니다.
from collections import deque
import sys
input = sys.stdin.readline
def bfs(r,c): # bfs 탐색
dist = [[0] * m for _ in range(n)] # 각 노드에 대한 거리를 관리하는 별도의 2차원 배열 dist
dr = [-1,1,0,0]
dc = [0,0,-1,1]
visited[r][c] = True # 해당 지점 방문처리
queue = deque()
queue.append((r,c))
while queue: # queue가 빌 때까지 계속 탐색
r, c = queue.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < m and board[nr][nc] == 'L' and not visited[nr][nc]:
dist[nr][nc] = dist[r][c] + 1 # 거리 갱신
visited[nr][nc] = True
queue.append((nr,nc))
return max(map(max,dist))
# n * m 보드 입력받기
n, m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]
answer = 0 # 최종 답
for i in range(n):
for j in range(m):
if board[i][j] == 'L': # 'L'인 지점에서
visited = [[False] * m for _ in range(n)] # visited 배열 초기화하고
answer = max(answer,bfs(i,j)) # bfs 탐색 후, 기존 answer과 비교
print(answer)
dist 변수를 0으로 설정하지 않고, 기존 거리를 저장하면서 나아갈 수 있는 2차원 배열을 만들어서 최단거리를 계산하도록 했습니다.
※ 'dist' 배열 사용시 장점
- 'dist' 배열은 각 노드에 도달하기 위한 실제 거리를 저장합니다. 즉, 시작점부터 각 노드까지의 최단 거리를 나타냅니다.
- BFS 에서는 한 노드를 방문할 때마다 그 노드의 이전 노드에서 거리에 1을 더해 'dist' 배열에 저장합니다. 이 방식은 각 노드별로 정확한 거리를 계산할 수 있게 해줍니다.
- 최종적으로, 'dist' 배열에서 가장 큰 값이 시작 노드로부터 가장 멀리 떨어진 노드까지의 최장거리가 됩니다.
즉, 'dist' 변수를 0으로 설정해서 사용하는 첫 번째 접근은 BFS 탐색 과정에서 큐에 들어간 노드의 총 수를 측정하는 것이며, 이는 실제 최장 거리와는 다릅니다. 반면, 'dist' 배열을 사용하면, 각 노드별로 정확한 거리를 계산할 수 있어, 이 문제에 더 적합한 방법입니다.
실제로, 아래 코드를 bfs() 함수에서 반환하기 전 찍어보면,
print()
for i in range(n):
for j in range(m):
print(dist[i][j],end="")
print()
아래와 같이 출력되는 것을 확인할 수 있다. 실제로 bfs()를 통해 탐색하면서 무조건적으로 1을 증가시키는 것이 아니라 최단경로를 보장하면서 계산되는 것을 확인할 수 있다.
그렇게 문제를 다 푼 줄 알았지만, 이번에는 시간초과 문제에 직면했습니다. 물론 pypy로는 통과됐습니다만, python으로 돌리면 역시 55% 쯤에서 시간초과가 났었습니다.
보통 이런 그래프 탐색 알고리즘에서 시간초과 문제를 개선하는 방법으로는 크게 4가지로 나눠서 설명할 수 있습니다.
1. 불필요한 BFS 호출 최소화
- 현재까지의 코드에서는 모든 'L' 지점에서 BFS를 호출합니다. 그러나 이렇게 하면, 많은 중복된 경로를 탐색하게 되어 시간이 오래 걸릴 수 있습니다. 보다 효율적인 접근 방법은 먼저 'L' 지점들을 찾아 리스트에 저장한 후, 그 리스트에서만 BFS를 호출하는 것입니다.
2. 가지치기(Pruning) 추가
- BFS를 수행하는 도중에, 이미 찾은 최장 거리보다 작거나 같은 거리의 경로는 더 이상 탐색하지 않도록 하는 것입니다. 이는 탐색 과정을 상당히 줄일 수 있고, 시간 복잡도를 개선하는 데 도움이 됩니다.
3. 입력 처리 방법 개선
- 'input = sys.stdin.readlin' 은 입력 처리를 빠르게 하기 위한 좋은 방법입니다. (물론, 문제에 따라 이러한 시간 최적화가 크게 영향을 주지 않을 수 있습니다.)
4. 파이썬 최적화 기법 사용
- 파이썬에서는 반복문, 재귀 호출 등에 대한 최적화 기법들이 있습니다. 리스트 컴프리헨션이나 내장함수를 적극적으로 사용할 수 있습니다.
가장 보편적으로 해결할 수 있는 방법은 1번과 2번입니다. 즉, 얼마나 덜 탐색을 하냐의 싸움인 것이죠. 로직은 같아도 순회를 덜 하거나 탐색을 덜하면 더 빠르게 문제를 해결할 수 있겠죠!?
그렇다면, 탐색을 줄여주는 방법으로는 어떤 것이 있을까요?
모든 'L' 지점에서 BFS를 수행하는 대신, 최초의 'L' 지점에서만 BFS를 수행하여 가장 먼 거리에 있는 지점을 찾을 수 있습니다.
또, 코드 최적화를 통해 불필요한 중복탐색을 최소화하는 방법도 있겠죠.
개선된 코드는 아래와 같습니다.
from collections import deque
import sys
input = sys.stdin.readline
def bfs(r,c):
dist = [[0] * m for _ in range(n)]
dr = [-1,1,0,0]
dc = [0,0,-1,1]
visited[r][c] = True
queue = deque()
queue.append((r,c))
while queue:
r, c = queue.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < m and board[nr][nc] == 'L' and not visited[nr][nc]:
dist[nr][nc] = dist[r][c] + 1
visited[nr][nc] = True
queue.append((nr,nc))
return max(map(max,dist))
n, m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]
land = []
answer = 0
for i in range(n):
for j in range(m):
if board[i][j] == 'L':
land.append((i,j))
if len(land) == n*m:
print(m+n-2)
else:
for i,j in land:
visited = [[False] * m for _ in range(n)]
answer = max(answer, bfs(i, j))
print(answer)
달라진 부분은 land 라는 배열을 따로 만들어서, 애초에 해당 지점이 'L'인 위치를 저장했다는 점입니다. 그런데, 이렇게 land를 따로 설정한 이유가 빛을 발하는 순간이 없어보입니다. 실제로 기존코드는 python3 로도 통과가 되는데, 위 코드에서는 land 라는 배열을 따로 만들어서 탐색할 bfs()를 줄였다기보다는 다른 이유로 bfs()를 줄였다고 볼 수 있습니다.
바로, if len(land) == n*m: print(n+m-2) 부분 때문입니다.
board 가 모두 'L'로 구성되어 있는 경우에는 최단경로가 보장된 최장경로는 'm+n-2' 경우의 수이기 때문에, 테스트케이스에서 board 가 모두 'L'로 구성되어 있을 때는 bfs() 를 타지 않고 대신, 바로 if 문을 타고 print(m+n-2) 을 찍습니다.
정말 우리의 목표인 bfs()에서의 중복탐색을 줄이기보다는 edge case에 대한 예외처리를 한 것에 가깝다고 할 수 있죠.
우리의 목표인 bfs() 로직을 쓰면서 모든 'L' 을 탐색하기보다 불필요한 탐색을 줄이는 방법은 그럼 어떻게 하면 될까요?
개선된 코드는 아래와 같습니다.
from collections import deque
import sys
input = sys.stdin.readline
def bfs(r,c):
dist = [[0] * m for _ in range(n)]
dr = [-1,1,0,0]
dc = [0,0,-1,1]
visited[r][c] = True
queue = deque()
queue.append((r,c))
while queue:
r, c = queue.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < m and board[nr][nc] == 'L' and not visited[nr][nc]:
dist[nr][nc] = dist[r][c] + 1
visited[nr][nc] = True
queue.append((nr,nc))
return max(map(max,dist))
n, m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]
answer = 0
for i in range(n):
for j in range(m):
if board[i][j] == 'L':
visited = [[False] * m for _ in range(n)]
if 0 <= i - 1 and i + 1 < n:
if board[i - 1][j] == 'L' and board[i + 1][j] == 'L':
continue
if 0 < j - 1 and j + 1 < m:
if board[i][j - 1] == 'L' and board[i][j - 1] == 'L':
continue
answer = max(answer, bfs(i, j))
print(answer)
기존 코드에서 'L'을 탐색하는데,
1. 바라보고 있는 'L'을 기준으로 (상,하,좌,우)가 board 범위 안으로 들어오고,
2. 해당 (상,하,좌,우)가 역시 'L' 이면 굳이 bfs()를 탐색할 필요가 없습니다. 어차피 중복탐색이기 때문이죠.
이러한 중복탐색만 피해줘도, 시간은 훨씬 단축됩니다.
마지막 위 코드가 우리가 원하는 효율적인 bfs() 코드입니다.
단순, edge 케이스에 대한 예외를 찾는 것보다 본질적으로 어떻게 탐색을 덜 할까에 대한 고민을 한다면, bfs()를 시작하기 전에 필요한 부분만 탐색하는 방안을 찾으실 수 있을 것입니다.
이번 문제를 통해, 우리가 짚고 넘어가야 할 점은 다음과 같이 정리할 수 있겠습니다.
1. 최단경로에 대한 거리계산은 새로운 변수를 사용해서 1씩 증가하는 것보다 이전 노드를 기준으로 cost를 계산해야 최단경로가 보장됩니다.
2. bfs() 문제에서 시간초과가 나올 때는 bfs() 탐색을 줄일 수 있는 방법으로, 필요한 부분만 탐색할 수 있게 미리 탐색 리스트를 선별하는 것을 고려해야 합니다. 이 때, 단순 edge case를 피하는 코드가 아니라, 실제 탐색하는 bfs()가 적게 호출되는지 생각해봐야 합니다.
3. BFS 문제에서는 visited 배열을 초기화하는 타이밍이 중요한데, 보통 한 bfs()를 탐색하고 또 다른 bfs()가 시작되기 전 초기화된 visited로 또 다시 탐색을 합니다.
bfs 문제 주의할 점들을 이제 까먹지 맙시다! 특히 문제를 풀 때, 1번과 2번에 대해 한 번 유심히 생각해보는 습관을 가집시다!
'컴퓨터 공부 > 📚 Baekjoon(백준)' 카테고리의 다른 글
| [백준/알고리즘/python/java] 2636번 - 치즈 (2) | 2023.11.21 |
|---|---|
| [백준/알고리즘/python/java] 14502번 - 연구소 (4) | 2023.11.21 |
| [백준/알고리즘/python/java] 2852번 - NBA 농구 (0) | 2023.11.16 |
| [백준/알고리즘/python/java] 14499번 - 주사위 굴리기 (2) | 2022.12.12 |
| [백준/알고리즘/python/java] 1976번 - 여행 계획 (0) | 2022.12.11 |