문제
풀지 못한 이유
- 문제를 보자마자 BFS로 풀어야겠다고 생각했고, '이것이 코딩 테스트다' 책에서 풀어본 미로탈출 문제가 생각났다.
- 하지만 직접 코드를 작성하진 못했고, 전에 풀었던 미로탈출 문제를 참고하여 작성했다. 아무래도 BFS 개념은 이해했지만 직접 코드를 작성할 수 있을 때까지 더 연습이 필요한 것 같다.
풀이) BFS
BFS는 너비 우선 탐색으로 그래프에서 가까운 노드부터 우선적으로 탐색한다. 큐를 이용해서 구현할 수 있다. 파이썬에서 큐는 collections의 deque를 이용하자. BFS의 과정은 다음과 같다.
- 시작 노드를 큐에 넣고 방문 처리하기
- 큐에서 노드를 꺼내고(popleft()) 인접 노드 중 방문하지 않은 노드를 큐에 넣고 방문 처리하기
- 큐에 노드가 없을 때까지 2번 과정 반복하기
참고: [이것이 코딩 테스트다 with Python] 19강 BFS 알고리즘
from collections import deque
def solution(maps):
answer = 0
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque()
queue.append((x, y))
# queue가 빌 때까지 반복
while queue:
x, y = queue.popleft()
# 상하좌우 칸 확인하기
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 맵을 벗어나면 무시하기
if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]): continue
# 벽이면 무시하기
if maps[nx][ny] == 0: continue
# 처음 지나가는 길이면 거리계산하고 다시 상하좌우 확인하기
if maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1
queue.append((nx, ny)) # 재귀
# 상대 팀 진영(제일 오른쪽 아래 칸)까지의 거리 반환
return maps[len(maps)-1][len(maps[0])-1]
answer = bfs(0, 0)
return -1 if answer == 1 else answer # 상대 팀 진영에 도착할 수 없을 때 -1그럼 코드를 꼼꼼히 살펴보자.
문제에서 캐릭터는 동, 서, 남, 북(상하좌우)으로만 움직일 수 있다고 했다. 따라서 BFS에서 상하좌우를 확인하기 위한 dx, dy 리스트를 만든다. 여기서 상하좌우는 2차원 리스트를 상상하면 이해가 될 것이다. dx는 행을 이동하고 dy는 열을 이동하는 것이다.
# 상:(-1, 0), 하:(1, 0), 좌:(0, -1), 우:(0, 1)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]다음으로 bfs 함수 안을 보면, 우선 큐를 만들고 큐에 인자로 받은 x와 y를 튜플 형식으로 넣는다. 여기서 x, y는 캐릭터가 서있는 칸의 좌표로 이 칸을 기준으로 상하좌우를 확인해 볼 것이다.
def bfs(x, y):
queue = deque()
queue.append((x, y))이제 큐가 빌 때까지 다음 작업을 반복한다. 큐는 선입선출이기 때문에 제일 먼저 넣은 값이 제일 먼저 나온다. 따라서 현재 캐릭터가 서있는 칸의 좌표인 x와 y를 큐에서 꺼낸다.
현재 캐릭터가 서있는 칸을 기준으로 상하좌우 칸을 확인하는데, 맵을 벗어나거나 벽인 경우에는 넘어간다. 그리고 처음 방문한 칸이면 첫 번째 칸(문제에서는 (1, 1)이지만 (0, 0)으로 계산)부터 이 칸까지의 거리를 계산하여 갱신한다. 그리고 이 칸의 좌표를 큐에 넣어 다음에 이 칸에서의 상하좌우를 확인할 수 있도록 한다.
이렇게 모든 칸의 거리 계산이 끝났으면 상대 팀 진영인 제일 오른쪽 아래 칸의 거리 값을 반환한다.
# queue가 빌 때까지 반복
while queue:
x, y = queue.popleft()
# 상하좌우 칸 확인하기
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 맵을 벗어나면 무시하기
if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]): continue
# 벽이면 무시하기
if maps[nx][ny] == 0: continue
# 처음 지나가는 길이면 거리계산하고 다시 상하좌우 확인하기
if maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1
queue.append((nx, ny)) # 재귀
# 상대 팀 진영(제일 오른쪽 아래 칸)까지의 거리 반환
return maps[len(maps)-1][len(maps[0])-1]최종적으로 위에서 구한 상대 팀 진영까지의 거리를 반환하는데, 문제에서 상대 팀 진영에 도달할 수 없는 경우는 -1을 반환하라고 했으므로 이를 처리한다.
answer = bfs(0, 0)
return -1 if answer == 1 else answer # 상대 팀 진영에 도착할 수 없을 때 -1회고
BFS는 큐를 이용해 구현하고, 방문 여부에 따라 작업한다는 것을 잊지 말자. 전에 BFS 문제를 풀었을 때도 혼자서 코드를 작성하지 못했는데, 아마도 개념만 이해하고 구현 과정을 제대로 살펴보지 않아서 그런 것 같다. 다음에는 반드시 직접 풀어서 맞추도록 하자.
