문제 링크
https://www.acmicpc.net/problem/13460
🕒 Python 풀이시간: 45분
from collections import deque
n,m=map(int,input().split())
dx=[0,0,-1,1]
dy=[-1,1,0,0]
bluePos=[]
redPos=[]
board=[]
visited=set()
for i in range(n):
arr=list(input())
for j in range(m):
if arr[j]=='B':
bluePos=[i,j]
if arr[j]=='R':
redPos=[i,j]
board.append(arr)
q=deque()
q.append((redPos[0],redPos[1],bluePos[0],bluePos[1],0))
visited.add((redPos[0],redPos[1],bluePos[0],bluePos[1]))
answer=-1
while q:
rx,ry,bx,by,cnt=q.popleft()
if cnt>=10:
break
for i in range(4):
nrx,nry,nbx,nby=rx,ry,bx,by
distR=0
distB=0
while board[nrx+dx[i]][nry+dy[i]]!='#' and board[nrx][nry]!='O':
nrx=nrx+dx[i]
nry=nry+dy[i]
distR+=1
while board[nbx+dx[i]][nby+dy[i]]!='#' and board[nbx][nby]!='O':
nbx=nbx+dx[i]
nby=nby+dy[i]
distB+=1
if board[nbx][nby]=='O':
continue
if (nrx,nry,nbx,nby) in visited:
continue
if board[nrx][nry]=='O':
answer=cnt+1
break
if nrx==nbx and nry==nby:
if distR>distB:
nrx-=dx[i]
nry-=dy[i]
else:
nbx-=dx[i]
nby-=dy[i]
visited.add((nrx,nry,nbx,nby))
q.append((nrx,nry,nbx,nby,cnt+1))
if answer!=-1:
break
print(answer)구슬 탈출 게임 시뮬레이션! 🔴🔵🚪
구슬 탈출 게임을 진행하는 시뮬레이션 문제이며 BFS 문제이다. 각 구슬은 동시에 진행되므로 이 점에 유의하여야 한다. 한 반년 전에 삼성 역량테스트 문제집을 백준에서 풀이하다가 이 문제 빼고는 다 풀었었는데 지금 좀 성장을 한건지 이제 한번에 풀었다 휴...
빨간 구슬과 파란 구슬이 동시에 움직이기 때문에 이 점에 유의하여야 하는데 이 때, 동시에 움직임을 끝마친 상태를 기준으로 visited를 기록해야 한다. 동시에 움직인 기록을 최단 거리로 측정해서 가지고 가기 때문이며 동시에 이미 한 위치에 가면 그 위치를 다시 탐색할 필요가 없기 때문이다.
현재 지점을 기준으로 해서 기존의 BFS와 마찬가지로 4가지 방향으로 움직인다. 이 때, 구멍이 있거나 벽이 있지 않은 지점까지 끝까지 이동해야 한다. 그 이유는 문제에서 한 번 기울였을 때, 끝까지 구슬이 움직이기 때문이다. 움직인 후의 좌표를 구했다면 먼저 파란 구슬이 들어갔는지를 판단해야 한다. 파란 구슬이 먼저든 나중이든 이번 케이스에 한해서 들어간다면 실패이므로 continue 해준다. 또한 방문한 구슬의 위치라면 이 또한 continue해준다. 만약 빨간 구슬만 들어갔다면, 이 경우에는 파란 구슬이 들어갔는지 여부를 이미 위에서 체크해주었기 때문에 자연스럽게 빨간 구슬만 들어간 경우만 따지게 된다. 빨간 구슬만 들어갔다면 답을 출력하고 종료하면 된다.
만약 이런 체크 후에 두 구슬의 위치가 겹친다면 늦게 온 공이 즉, 거리가 더 멀었던 공의 좌표를 보정해주어야 한다. 온 방향으로 뒤로 한칸 이동해주면 된다. 그리고 기존의 BFS와 마찬가지로 큐와 visited에 기록해주면 끝난다.
이렇게 Python으로 백준의 "구슬 탈출 2" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
