백준 16954 문제 링크: https://www.acmicpc.net/problem/16954
📑 문제 설명
8x8 벽이 움직이는 체스판에서 탈출하기
0. 가장 왼쪽 아랫칸에서 시작
1. 1초마다 벽이 아래에 있는 행으로 한 칸씩 이동 --> 맵그래프가 매번 수정됨
- 가장 아래에 있어서 행이 없다면 해당 벽은 사라지게 된다.
2. 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동, 아니면 이동하지 않을 수 있다.
- 이동할 때는 빈 칸으로만 이동 가능
3. 캐릭터가 먼저 이동한 후 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 캐릭터는 더 이상 이동할 수 없다
4. 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지/없는지 구해보자
입력:
8개 줄에 걸쳐 체스판 상태가 주어짐
'.': 빈칸, '#':벽
- 단, 가장 왼족 아랫칸은 항상 벽이 아니다
출력: 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력
💡 문제 해결 방법
알고리즘: BFS
알고리즘 선택 이유
예외처리 및 추가 내용
1. 시작점: 7, 0 --> 도착점: 0, 7
2. 캐릭터가 8방향 + 가만히 있음에서 하나를 선택하여 이동
3. 그래프를 1초마다 업데이트 해야 함
- 벽의 위치를 파악하여 행 + 1을 해주고 벽이 이동한 곳은 '.'(빈칸)으로 수정
스터디 내용
1. time step 마다 미로가 변경됨 & 움직이는 방향 9개
2. queue에 현 위치 pop
- 벽이 아닌 곳으로 이동(queue에 삽입)
- 벽 이동 시킴
- queue를 다시 보면서 벽이랑 위치가 같은 경우 탐색 X
3. visit은 고려하지 않아도 됨
💻 코드
import sys
from collections import deque
graph = [[] for x in range(8)]
walllist = []
for i in range(8):
temp = sys.stdin.readline()
for j in range(8):
graph[i].append(".")
if temp[j] == "#":
walllist.append([i, j])
# start: 7, 0 // end: 0, 7
def bfs():
cnt = 0
q = deque([(7, 0)]) # x, y
while q:
for _ in range(len(q)):
x, y = q.popleft()
if [x,y] in walllist:
continue
if x == 0 or cnt == 9:
print(1)
return
adjlist = [[0, 0], [1, 0], [-1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]]
for addx, addy in adjlist:
nx = addx + x
ny = addy + y
if nx >= 0 and nx < 8 and ny >= 0 and ny < 8:
if [nx, ny] not in walllist:
q.append((nx, ny))
for i in range(len(walllist)):
walllist[i] = [walllist[i][0]+1, walllist[i][1]]
cnt+=1
print(0)
if len(walllist) == 0:
print(1)
else:
bfs()💟 추가적으로 알게 된 점
1. queue를 사용할 때 반드시 필요없는 정보가 과도하게 많이 들어가지 않는지 확인하기
- 움직이는 미로 탈출 문제는 9방향 어디나 갈 수 있으며 visit 배열을 사용하게 되면 이미 온 곳은 다시 방문할 수 없다고 생각하여 과감하게 visit을 생략했음
- 여기서 핵심은 주인공이 0행에 도달하거나 9초 동안 살아남아 있을 경우 반드시 오른쪽상단에 도착할 수 있음(1초마다 벽이 내려가서 사라지기 때문에)
2. 여기서 내가 놓쳤던 부분은 1초마다 벽이 움직이는 것과 주인공이 한 칸씩 이동하는 것을 매핑시켜야 한다는 것
- 다시 말해서 1초동안 움직일 수 있는 방향은 9방향이며 9방향동안 움직이면서 탐색할 경우에는 벽이 움직이면 안됨 --> 나같은 경우는 9방향 움직일 때마다 벽을 움직이도록 설정해서 조금 애를 먹었음
- 이걸 해결할 수 있는 방법은 while q안에 for 반복문을 사용하거나 cnt와 같은 변수로 초를 공유할 수 있도록 유도해야 함
