💡 문제
N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.
버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.
- 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
- 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
- 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)
둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.
- o: 동전
- .: 빈 칸
- #: 벽
동전의 개수는 항상 2개이다.
출력
첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.
💭 접근
보드 위에 올려진 두 동전 중 하나의 동전만 떨어졌을 때의 최소 버튼 입력을 구해야 하는 문제이므로 우선 버튼 입력에 따라 두 동전의 위치를 각각 계산한 뒤, 각 동전이 떨어졌는지를 판단해야 한다.
또한 한 개의 동전이 떨어지기까지의 최소 버튼 입력을 구해야 하므로 BFS를 사용할 수 있다.
- 두 동전의 좌표 저장하기
coin_pos = []
for i in range(n): # 1
for j in range(m):
if graph[i][j] == "o":
coin_pos.append([i, j])- BFS 함수를 호출하고, 각 동전의 좌표와 버튼을 누른 횟수를
q에 저장한다.
def bfs():
global ans_flag
q = deque()
q.append((coin_pos[0][0], coin_pos[0][1], coin_pos[1][0], coin_pos[1][1], 0)) # 2- 이후 두 동전을 상하좌우로 이동시킨다.
coin_0_x, coin_0_y, coin_1_x, coin_1_y, cnt = q.popleft()
for i in range(4): # 3
coin_0_nx = coin_0_x + dx[i]
coin_0_ny = coin_0_y + dy[i]
coin_1_nx = coin_1_x + dx[i]
coin_1_ny = coin_1_y + dy[i]- 동전을 한 칸씩 이동시킨 다음,
check_drop()함수를 호출하여 동전이 떨어졌는지를 판단한다.
def check_drop(x, y):
if x < 0 or x >= n or y < 0 or y >= m:
return True
return False
# 4
coin_0_flag = check_drop(coin_0_nx, coin_0_ny)
coin_1_flag = check_drop(coin_1_nx, coin_1_ny)- 한 개의 동전만 떨어졌는지 (종료조건) 확인한다.
if (coin_0_flag and not coin_1_flag) or (not coin_0_flag and coin_1_flag): # 5
print(cnt + 1)
ans_flag = True
break- 조건을 만족하지 못했다면 다음 좌표가 벽인지에 따라
q에 새로운 좌표 append
이때 버튼의 입력 횟수가 10을 넘기면 안되기 때문에 이때까지 버튼을 누른 횟수가 9보다 작을 때만 실행한다.
if cnt < 9:
if 0 <= coin_0_nx < n and 0 <= coin_0_ny < m and 0 <= coin_1_nx < n and 0 <= coin_1_ny < m: # 6
if graph[coin_0_nx][coin_0_ny] == '#':
coin_0_nx = coin_0_x
coin_0_ny = coin_0_y
if graph[coin_1_nx][coin_1_ny] == '#':
coin_1_nx = coin_1_x
coin_1_ny = coin_1_y
q.append((coin_0_nx, coin_0_ny, coin_1_nx, coin_1_ny, cnt + 1))📒 코드
from collections import deque
def bfs():
global ans_flag
q = deque()
q.append((coin_pos[0][0], coin_pos[0][1], coin_pos[1][0], coin_pos[1][1], 0)) # 2
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while q:
if ans_flag:
break
coin_0_x, coin_0_y, coin_1_x, coin_1_y, cnt = q.popleft()
for i in range(4): # 3
coin_0_nx = coin_0_x + dx[i]
coin_0_ny = coin_0_y + dy[i]
coin_1_nx = coin_1_x + dx[i]
coin_1_ny = coin_1_y + dy[i]
# 4
coin_0_flag = check_drop(coin_0_nx, coin_0_ny)
coin_1_flag = check_drop(coin_1_nx, coin_1_ny)
if (coin_0_flag and not coin_1_flag) or (not coin_0_flag and coin_1_flag): # 5
print(cnt + 1)
ans_flag = True
break
if cnt < 9:
if 0 <= coin_0_nx < n and 0 <= coin_0_ny < m and 0 <= coin_1_nx < n and 0 <= coin_1_ny < m: # 6
if graph[coin_0_nx][coin_0_ny] == '#':
coin_0_nx = coin_0_x
coin_0_ny = coin_0_y
if graph[coin_1_nx][coin_1_ny] == '#':
coin_1_nx = coin_1_x
coin_1_ny = coin_1_y
q.append((coin_0_nx, coin_0_ny, coin_1_nx, coin_1_ny, cnt + 1))
def check_drop(x, y):
if x < 0 or x >= n or y < 0 or y >= m:
return True
return False
n, m = map(int, input().split())
graph = [list(input()) for _ in range(n)]
coin_pos = []
for i in range(n): # 1
for j in range(m):
if graph[i][j] == "o":
coin_pos.append([i, j])
ans_flag = False
bfs()
if not ans_flag:
print(-1)💭 후기
천천히 동전의 동작 방식을 먼저 구상하고 차례대로 코드로 옮기니 어렵지 않게 해결할 수 있었다.
🔗 문제 출처
https://www.acmicpc.net/problem/16197
精進 "정성을 기울여 노력하고 매진한다"