https://softeer.ai/practice/7726/history?questionType=ALGORITHM
지도 상에 나타나는 정보 : 남우, 출구, 유령, 빈공간, 벽
. : 빈칸
D : 탈출구
G : 귀신
# : 벽
N : 남우
1초에 한 칸씩 상하좌우로 이동
유령은 벽을 통과할 수 있음
유령은 자기 자리에서 움직이지 않을 수 있음
남우가 유령과 마주치면 잡힘 (출구 자리라도)
입력
첫 번째 줄 : n, m
n : 행
m : 열
나머지 줄 : 행렬 정보
출력
탈출 가능하면 Yes
탈출 불가능하면 No
BFS로 풀 수 있는 턴제형 미로 문제입니다.
문제에서 명시가 되어 있는 것은 아니지만 매 턴마다 남우가 먼저 움직이고 난 후 나머지 귀신이 움직이는 순서로 되어 있습니다.
이에 맞춰 처음 queue에 남우와 귀신 정보를 저장할 때 남우를 먼저 넣고나서 귀신 정보를 넣도록 구현하였습니다.
일반적으로 백준 등에 존재하는 미로 문제들과 다른 점은 귀신이 벽을 통과할 수 있다는 점이고, 귀신이 멈춰설 수 있다는 점인데,
이를 해결하기 위해서 남우의 방문처리(nv)와 귀신의 방문처리(gv)를 별도로 진행하였습니다.
import sys
from collections import deque
def print_arr(arrs):
for i in range(len(arrs)):
for j in range(len(arrs[0])):
print(arrs[i][j], end=" ")
print()
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def bfs():
global n, m, q, ans, nv, gv
while len(q) != 0:
px, py, pc = q.popleft()
for d in range(4):
nx = dx[d] + px
ny = dy[d] + py
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 남우일 때
if pc == 'N':
if nv[nx][ny] == True or gv[nx][ny] == True or arr[nx][ny] == '#':
continue
# 탈출구를 만나면
if arr[nx][ny] == 'D':
ans = 'Yes'
return
nv[nx][ny] = True
q.append([nx, ny, pc])
# 유령일 때
elif pc == 'G':
if gv[nx][ny] == True:
continue
gv[nx][ny] = True
q.append([nx, ny, pc])
n, m = list(map(int, input().split()))
arr = []
for _ in range(n):
arr.append(list(map(str, input().strip())))
other = []
q = deque()
nv = [[False] * m for _ in range(n)]
gv = [[False] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if arr[i][j] == 'N':
q.append([i, j, 'N'])
nv[i][j] = True
elif arr[i][j] == 'G':
other.append([i, j, 'G'])
gv[i][j] = True
q.extend(other)
ans = 'No'
bfs()
print(ans)
~~
해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.
혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!
python source : https://github.com/ssh5212/conding-test-practice
java source : https://github.com/ssh5212/coding-test-java
[BOJ / 백준] 2668 숫자고르기 (G5^ / DFS) - Python (0) | 2024.07.02 |
---|---|
[BOJ / 백준] 16562 친구비 (G4 / DFS) - Python (0) | 2024.06.30 |
[BOJ / 백준] 15971 두 로봇 (G4^ / DFS) - Python (0) | 2024.06.28 |
[BOJ / 백준] 2644 촌수계산 (S2 / DFS) - Python (0) | 2024.06.27 |
[BOJ / 백준] 2606 바이러스 (S3 / DFS) - Python (0) | 2024.06.26 |