두 동전
문제
NXM 크기의 보드와 4개의 버튼으로 이루어진 게임이 있습니다. 보드는 1X1 크기의 정사각형 칸으로 나누어져 있습니다. 각각 칸은 비어있거나 벽입니다. 두개의 빈칸에는 동전이 하나씩 놓여져있고 두 동전의 위치는 다릅니다.
버튼은 왼쪽/오른쪽/위/아래와 같이 4가지가 있습니다.
버튼을 누르면 두 동전은 동시에 버튼에 쓰여져있는 방향으로 이동합니다.
- 동전이 이동하려는 칸이 벽이면 동전은 이동하지 않습니다.
- 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어집니다.
- 그 이외의 경우에는 이동하려는 방향으로 한칸 이동합니다. (동전이 곂쳐도 됩니다.)
한 동전만을 보드에서 떨어뜨리기 위해 최소한으로 버튼을 몇번 눌러야하는지를 구하는 문제입니다.
제약조건
- 세로 N, 가로 M 일때 1 <= N,M <= 20
- 버튼을 10번 보다 많이 누르는 경우 -1을 반환합니다.
풀이
BFS 알고리즘을 이용했습니다. queue에는 최소한으로 이동했을때, 이동가능한 두 동전의 발견된 위치들을 저장합니다.
queue의 크기 단위로 버튼 누르는 횟수를 셉니다.
다음과 같은 경우 queue에 집어넣지 않습니다.
- 두 동전이 동시에 떨어짐. -> 더 이상 이동가능하지 않습니다. 따라서 queue의 정의에 따라 queue에 넣을수없습니다.
- 두 동전이 이동하지 않음 / 두 동전이 이미 발견됨. -> 해당 경우는 이동가능하지만 문제에서 최소한의 버튼을 누르는것을 요구하기 때문에 답이 무조건 될수없으므로 queue에 넣지 않습니다.
- 두 동전중 하나만 떨어짐. -> 답을 발견했으므로 더 이상 진행할 필요가 없습니다.
위의 경우를 제외한 경우는 queue에 집어넣습니다.
queue의 크기가 0이 되거나 버튼 누른횟수가 10을 넘어갈경우, -1을 반환합니다.
코드
'''
Created by jun on 21/05/25
'''
import collections
buttons = [(0, -1), (0, 1), (-1, 0), (1, 0)] #y, x
N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
coins = list()
for y in range(N):
for x in range(M):
if board[y][x] == 'o':
coins.append((y, x))
# ((3, 0), (4, 0))
def bfs(coins):
discovered = set()
discovered.add(coins)
queue = collections.deque()
queue.append(coins)
cnt = 0
while queue and cnt < 10:
cnt += 1
for _ in range(len(queue)):
coin1, coin2 = queue.popleft()
for button in buttons:
dropped_coin = 0
#새로운 동전의 위치
new_coin1 = (coin1[0] + button[0], coin1[1] + button[1])
new_coin2 = (coin2[0] + button[0], coin2[1] + button[1])
#동전 위치 조정
#동전 1이 떨어진 경우 / 범위를 벗어난 경우.
if not(0 <= new_coin1[0] < N and 0 <= new_coin1[1] < M):
dropped_coin += 1
#동전 1이 #인경우
#버튼 조작을 취소한다.
elif board[new_coin1[0]][new_coin1[1]] == '#':
new_coin1 = (coin1[0], coin1[1])
#동전 2가 떨어진경우
if not(0 <= new_coin2[0] < N and 0 <= new_coin2[1] < M):
dropped_coin += 1
# 동전 2이 #인경우
# 버튼 조작을 취소한다.
elif board[new_coin2[0]][new_coin2[1]] == '#':
new_coin2 = (coin2[0], coin2[1])
# 예외처리 : 이미 방문한 경우 / 안 움직인 경우
# 모든 조작이 완료된 상태
if (new_coin1, new_coin2) in discovered:
continue
#하나도 안떨어진 경우 -> 재평가
if dropped_coin == 0:
queue.append((new_coin1, new_coin2))
discovered.add((new_coin1, new_coin2))
#하나만 떨어진경우 -> 정답
elif dropped_coin == 1:
return cnt
#둘다 떨어진경우 -> 평가 종료.
return -1
print(bfs(tuple(coins)))
새로 알게된 사실
판에서 동전을 이동시키는 법
move 함수를 선언해서 이동한 y,x를 반환하면 깔끔하게 짤수있다. (이동 불가할땐 -1 반환)
Author And Source
이 문제에 관하여(두 동전), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@6047198844/두-동전저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)