[파이썬] 백준 16197. 두 동전(Python)

16197. 두 동전 바로가기

이 문제는 두 동전중 , 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성해야 한다.

문제 접근

• 사용 알고리즘 : BFS 최단 시간 알고리즘
• input 받으며 두 동전의 위치 좌표를 받는다.(x, y, xx, yy)
• bfs 함수에서 두 동전 좌표를 인자로 받는다.
• 함수 시작하며 check 라는 두 동전의 위치를 확인하기 위한 4차원 배열을 만든다.
• 그리고 두 동전의 첫 위치를 0으로 표시하고 큐에 담는다.
• 큐에 값이 있는 동안 큐에서 값을 하나씩 꺼내며 너비우선탐색으로 갈 수 있는 곳을 퍼트린다.
• 큐에서 꺼낸 위치 값이 이미 10번 이상이면 실패이므로 while문을 빠져나가 -1을 리턴한다.
• 그렇지 않다면 4방향 이동할 위치를 탐색한다.
• 고려해줄 경우는 다음과 같다.
  • 두 동전 모두 이동할 위치가 격자 밖이면 continue
  • 위에서 걸러지므로 둘 중 한 동전만 격자 밖이면 현재 위치값 + 1한 값을 리턴한다.
  • 이동할 곳이 벽이면 이동하지 않으므로 원 위치 시킨다.
  • 이동할 곳이 첫 방문일 경우에만 새 위치에 현 위치 + 1한 값으로 표시하고 큐에 담는다.

조건만 잘 정리해서 코드에 적용하면, BFS 알고리즘으로 쉽게 적용하여 해결할 수 있다.

정답 코드

import sys
input=sys.stdin.readline
from collections import deque

def BFS(x,y,xx,yy):
    check=[[[[-1]*m for _ in range(n)] for _ in range(m)]for _ in range(n)]
    check[x][y][xx][yy]=0
    dq=deque([(x,y,xx,yy)])
    while dq:
        x,y,xx,yy=dq.popleft()
        if check[x][y][xx][yy] >=10:
            break
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            nxx=xx+dx[i]
            nyy=yy+dy[i]
            if not(0<=nx <n and 0<= ny <m) and not(0<=nxx <n and 0<= nyy <m):
                continue
            if not(0<=nx <n and 0<= ny <m):
                return check[x][y][xx][yy]+1
            if not(0<=nxx <n and 0<= nyy <m):
                return check[x][y][xx][yy]+1
            if a[nx][ny] =='#':
                nx-=dx[i]
                ny-=dy[i]
            if a[nxx][nyy] =='#':
                nxx-=dx[i]
                nyy-=dy[i]
            if check[nx][ny][nxx][nyy] == -1:
                check[nx][ny][nxx][nyy]= check[x][y][xx][yy]+1
                dq.append([nx, ny , nxx ,nyy])
    return -1
n,m=map(int, input().split())


cnt=0
dx=[-1,0,1,0]
dy=[0,1,0,-1]    

x,y,xx,yy=0,0,0,0
a=[]
flag=True
for i in range(n):
    a.append(list(input().rstrip()))
    for j in range(m):
        if a[i][j]=='o':
            if flag:
                x,y=i,j            
                flag=False
            else:
                xx,yy=i,j
print(BFS(x,y,xx,yy))