💡 문제
욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.
이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.
1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.
욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.
입력
8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.
출력
욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.
💭 접근
이 문제를 해결하기위해 방문처리를 어떻게 해야할지 고민하던 와중, 주인공이 목표지점에 도달했는지 여부와 이동횟수는 중요하지 않고, 벽이 다 사라질 때까지 주인공이 버틸 수 있다면 목표지점엔 반드시 도달할 수 있기 때문에 모든 벽이 사라질 때까지, 다시 말해 체스판의 높이는 8이기 때문에 벽이 8번 내려오는 동안 주인공이 벽과 만나지 않게 움직일 수만 있다면 1을 출력하도록 아래와 같이 구현하였다.
-
첫번째 종료조건 : 벽이 8번 내려갔는가? 또는 목표지점에 도달했는가? (혹시나 목표 지점에 도달할 수도 있으므로)
if cnt == 8 or (x == 0 and y == 7): # 1 return True우선 종료조건으로 벽이 내려온 횟수를 뜻하는
cnt변수가 8이 되었거나, 만약 주인공이 목표 지점에 도달했다면True를 return 하도록 첫번째 종료조건을 작성하였다. -
9가지의 방향으로 이동하면서 처음 확인해야 할 것 : 이동 가능한 장소인지 - 특히 이동하려는 곳에 벽이 있으면 이동하지 못함 (check_wall 함수)
dx = [0, -1, -1, 0, 1, 1, 1, 0, -1] dy = [0, 0, 1, 1, 1, 0, -1, -1, -1] for i in range(9): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < 8 and 0 <= ny < 8 and check_wall(nx, ny, wall):문제에서 주어진 작동 순서(주인공이 먼저 움직이고 벽이 내려옴)에 따라 주인공이 이동할 좌표를 업데이트하고 이미 벽이 있는 좌표로는 이동할 수 없으므로 이동할 위치에 벽이 있는지 확인한다.
def check_wall(nx, ny, wall): # 주인공이 이동하려는 방향에 벽이 있는지 확인하는 함수 for i in range(len(wall)): if wall[i][0] == nx and wall[i][1] == ny: return False return True이때
check_wall함수를 통해 벽과 존재하는지 간단하게 확인할 수 있다. -
이후 움직였으면 벽을 내릴 차례 (move_wall 함수) - 두번째 종료조건 : 벽이 8번 내려가지 않고도 모든 벽이 사라졌을 수도 있으니 벽의 갯수가 0이면 종료
n_wall = move_wall(wall) if len(n_wall) == 0: return True이제 문제에서 주어진 코드 작동 순서에 따라 주인공을 움직였다면, 벽을 내릴 차례이다.
def move_wall(wall): # 주인공이 이동한 후 모든 벽을 한칸씩 내리는 함수 n_wall = [] for i in range(len(wall)): if wall[i][0] + 1 < 8: n_wall.append((wall[i][0] + 1, wall[i][1])) return n_wall[:]이는
move_wall함수로 위와 같이 작성하였다. -
벽을 모두 내렸으면 주인공과 부딪히는지 확인 (check_hit 함수)
if check_hit(nx, ny, n_wall): continue이제 내린 벽과 이동시킨 주인공이 부딪히는지 확인한다.
def check_hit(nx, ny, n_wall): # 벽을 내린 후 주인공과 벽이 부딪히는지 확인하는 함수 for i in range(len(n_wall)): if n_wall[i][0] == nx and n_wall[i][1] == ny: return True return False이는
check_hit함수로 간단하게 구현하였다. -
마지막 종료조건 :
True를 return 하지 못하고 while문이 종료되면Falsereturn (주인공이 모든 경우에서 벽에 부딪힘)return False이제 마지막으로 1번 종료조건을 만족하지 못하고 모든 경우에서 주인공이 벽과 부딪혀 벽이 다 내려올 때까지 버티지 못했다면
bfs함수를 종료하면서False를 return한다.
📒 코드
from collections import deque
def bfs():
q = deque()
q.append((7, 0, 0, wall_pos[:]))
dx = [0, -1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 0, 1, 1, 1, 0, -1, -1, -1]
while q:
x, y, cnt, wall = q.popleft()
if cnt == 8 or (x == 0 and y == 7): # 1
return True
for i in range(9):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < 8 and 0 <= ny < 8 and check_wall(nx, ny, wall): # 2
n_wall = move_wall(wall) # 3
if len(n_wall) == 0:
return True
if check_hit(nx, ny, n_wall): # 4
continue
q.append((nx, ny, cnt + 1, n_wall[:]))
return False # 5
def check_wall(nx, ny, wall): # 주인공이 이동하려는 방향에 벽이 있는지 확인하는 함수
for i in range(len(wall)):
if wall[i][0] == nx and wall[i][1] == ny:
return False
return True
def move_wall(wall): # 주인공이 이동한 후 모든 벽을 한칸 씩 내리는 함수
n_wall = []
for i in range(len(wall)):
if wall[i][0] + 1 < 8:
n_wall.append((wall[i][0] + 1, wall[i][1]))
return n_wall[:]
def check_hit(nx, ny, n_wall): # 벽을 내린 후 주인공과 벽이 부딪히는지 확인하는 함수
for i in range(len(n_wall)):
if n_wall[i][0] == nx and n_wall[i][1] == ny:
return True
return False
graph = [list(input()) for _ in range(8)]
wall_pos = []
for i in range(8):
for j in range(8):
if graph[i][j] == '#':
wall_pos.append((i, j))
if bfs():
print(1)
else:
print(0)💭 후기
꼭 목표지점에 도달하는 것이 아닌, 문제에서 어떤 것을 정답으로 요구하는 지 잘 이해하고 문제풀이에 활용하는 시야를 넓혀야겠다.
🔗 문제 출처
https://www.acmicpc.net/problem/16954
