백준 온라인 저지, BFS / 16954번: 움직이는미로탈출 (파이썬 / , 백준 골드문제)
2022. 4. 6. 23:21ㆍ알고리즘/BFS
728x90
반응형
문제
욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.
이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.
1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.
욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.
입력
8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.
출력
욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.
예제 입력 1
........ ........ ........ ........ ........ ........ ........ ........
예제 출력 1
1
예제 입력 2
........ ........ ........ ........ ........ ........ ##...... ........
예제 출력 2
0
예제 입력 3
........ ........ ........ ........ ........ .#...... #....... .#......
예제 출력 3
0
예제 입력 4
........ ........ ........ ........ ........ .####### #....... ........
예제 출력 4
1
예제 입력 5
........ ........ ........ ........ #....... .####### #....... ........
예제 출력 5
0
접근 방법
- 0. 총 8개의 움직이는 미로에 대한 모양을 board에 저장한다.
- 1. BFS를 통해 몇 번 움직였는지에 대한 횟수와, 이동한 위치를 큐에 저장하여 board에 방문기록을 갱신한다.
- 2. 8번째로 움직였을 때 만약 이동할 수 있는 위치에 .이 있다면 1을 출력하고 이동할 수 없다면 0을 출력한다.
코드
# https://www.acmicpc.net/problem/16954
# 접근 방법
# 0. 총 8개의 움직이는 미로에 대한 모양을 board에 저장한다.
# 1. BFS를 통해 몇 번 움직였는지에 대한 횟수와, 이동한 위치를 큐에 저장하여 board에 방문기록을 갱신한다.
# 2. 8번째로 움직였을 때 만약 이동할 수 있는 위치에 .이 있다면 1을 출력하고 이동할 수 없다면 0을 출력한다.
from collections import deque
import copy
board = [[[x for x in input()] for _ in range(8)]]
for _ in range(7):
board.append([['.' for _ in range(8)]] + copy.deepcopy(board[-1][:7])) # 움직인 횟수를 index로 하는 board 초기화
queue = deque([]) # 큐 자료구조를 활용한 BFS
queue.append([0, 7, 0]) # 이동 횟수, x의 위치, y의 위치
is_arrive = False # 오른쪽 끝까지 갈 수 있는지 체크
while queue and not is_arrive:
cnt, x, y = queue.popleft()
for dx, dy in [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 0], [0, 1], [1, -1], [1, 0], [1, 1]]: # 움직일 수 있는 방향 설정
if 0<=x+dx<=7 and 0<=y+dy<=7 and board[cnt+1][x+dx][y+dy] == '.': # 다음에 움직일 위치가 벽이 내려오지 않는 곳인 경우 동작
if board[cnt][x+dx][y+dy] == '#': # 움직일 수 있는 위치인지 확인
continue
queue.append([cnt+1, x+dx, y+dy])
board[cnt+1][x+dx][y+dy] = 1
if cnt+1 == 7: # 모든 벽이 내려온 뒤에는 더이상 탐색하지 않고 오른쪽 위로 이동할 수 있기에 is_arrive는 True
is_arrive = True
if is_arrive:
print(1)
else:
print(0)728x90
반응형
'알고리즘 > BFS' 카테고리의 다른 글
| 백준 온라인 저지, BFS / 1707번: 이분그래프 (파이썬 / 백준 골드문제) (0) | 2022.05.24 |
|---|---|
| 백준 온라인 저지, BFS / 16948번: 데스나이트 (파이썬 / 백준 실버문제) (0) | 2022.05.13 |
| 백준 온라인 저지, BFS / 1707번: 이분그래프 (파이썬 / , 백준 골드문제) (0) | 2022.04.06 |
| 백준 온라인 저지, BFS / 3055번: 탈출 (파이썬 / , 백준 골드문제) (0) | 2022.03.29 |
| 백준 온라인 저지, BFS / 14940번: 쉬운최단거리 (파이썬 / , 백준 골드문제) (0) | 2022.01.02 |