1. 알고리즘 관련 공부
이번 주는 공부했던 알고리즘 지식을 정리하려 한다.
예제) 미로의 최단거리 통로(BFS)
7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈 출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다.
격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면
위와 같은 경로가 최단 경로이며 경로수는 12이다.
▣ 입력설명
7*7 격자판의 정보가 주어집니다.
▣ 출력설명
첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.
▣ 입력예제 1
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0
▣ 출력예제 1
12
해설)
BFS() 단골 문제인 최단 거리 탐색이다. 미로는 board라는 격자판으로 입력을 받고 이동해야하니 체크리스트가 필요하다.
하지만 여기서는 지나간 길을 1로 만들어서 체크할 것이다. 움직인 거리가 최종적인 값이므로 dis라는 값이 0으로 초기화된 격자판이 필요하다. 4방향 탐색이 필요하므로 dx = [-1,0,1,0], dy=[0,1,0,-1] 리스트들이 필요하고 큐가 돌면서 그 노드의 4방향을 탐색할 것이다.
여기서 탐색하는 방법이 BFS인 이유는 탐색하는 4방향이 같은 레벨에 머물고 있기 때문이다. 큐에 처음 노드의 좌표를 넣고 그 다음 큐에 값이 존재할 때까지 큐에서 값을 꺼내고 for문으로 4방향에 대한 좌표 적합(0부터 n-1 까지에 있는지)과 방문 검증을 한다. 검증이 되면 방문을 체크하고 전 dis 좌표에 있는 값을 다음 dis 좌표값에 +1을 해서 움직인 거리 체크 이후 그 노드를 다시 큐에 넣는다. 만약 도착 노드의 방문이 안 되어 있으면 도달을 못했다는 것이므로 -1을 출력하고 그게 아니면 도착 노드의 dis 값을 출력한다.
from collections import deque
# 최단 거리는 무조건 BFS 넓이 우선 탐색으로 푼다.
# 입력 데이터는 board라는 2차원 리스트에 받는다.
# 출발점을 0으로 초기화한다.
# 좌표를 이동하는 문제니 같은 레벨을 비교하는 BFS()로 푼다.
# 좌표 이동 문제 -> dis, ch 리스트 생성
# dis 리스트는 이동 거리 저장용
# ch는 방문 체크 리스트
# 출발점의 오른 쪽을 갈 수 있다. 혹은 아래 쪽을 갈 수 있다. => 이동 거리 + 1
dx = [-1,0,1,0]
dy = [0,1,0,-1]
board = [list(map(int, input().split())) for _ in range(7)]
dis = [[0]*7 for _ in range(7)]
Q = deque()
# 출발점
Q.append((0,0))
# 여기서는 방문 체크 리스트를 안 만들고 방문한 곳을 벽으로 만들 것이다.
board[0][0] = 1
while Q:
tmp = Q.popleft()
# 4 방향 탐색
for i in range(4):
# tmp는 튜플
x = tmp[0] + dx[i]
y = tmp[1] + dy[i]
# 경계선 밖으로 안 나가려면 아래 조건을 달아줘야한다.
if 0<=x<=6 and 0<=y<=6 and board[x][y] == 0:
# 방문 체크
board[x][y] = 1
# 이동 거리 갱신
dis[x][y] = dis[tmp[0]][tmp[1]] + 1
# 큐에 넣기
Q.append((x,y))
# 벽에 막혀서 출력 불가, 루트가 없다. -> 목적지의 이동 거리 갱신이 안 됐다.
if dis[6][6] == 0:
print(-1)
# 도착!
else:
print(dis[6][6])
