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

 

 

백준 16197번: 두 동전

문제 바로 가기

---

📌 문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

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

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.
o: 동전
.: 빈 칸
#: 벽

동전의 개수는 항상 2개이다.

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

🗺 환경

• N x M 크기의 보드에 2개의 동전이 놓여 있음
• 보드 구성 
  • .: 빈칸
  • #: 벽
  • o: 동전
• 버튼: 4개(왼쪽, 오른쪽, 위, 아래)를 눌러서 동전을 움직임

 

 

📃 규칙

• 벽(#)이면 동전은 멈춤
• 보드 밖으로 나가면 동전이 떨어짐
• 빈 칸이나 다른 동전이 있는 칸이면 한 칸 이동함

 

 

🎯 목표

• 두 동전 중 정확히 하나만 보드 밖으로 떨어뜨려야 함

 

 

🧨 제한

• 버튼을 최대 10번까지만 누를 수 있음

 

 

🔮 핵심 포인트

• 두 동전의 위치를 함께 관리해야 함
• 버튼을 누르면 동전 두 개가 동시에 움직임
• 최소 버튼 누리기 횟수를 구해야 함

 

 

 

 

 

 

 

 

 

 

💡 해결 방법

 

 

🧩 아이디어

 

BFS 알고리즘

• 최소 횟수를 묻는 문제임
• BFS는 모든 경우를 너비(단계별)로 탐색하여 가장 빠른 해결 방법을 찾아냄

 

 

BFS 탐색 흐름

1. 4개의 방향(위, 아래, 왼쪽, 오른쪽)으로 동전을 이동시켜 봄
2. 이동 결과 확인
   • 하나만 떨어졌으면 성공 → 버튼 누른 횟수 반환
   • 둘 다 떨어졌으면 실패 → 다음 경우로 넘어감
   • 둘 다 살아있으면 → 다음 상태로 이동
3. 버튼을 10번 이상 누르면 실패 처리 → -1 반환

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

 

 

1️⃣ Step 1: 입력 처리

n, m = map(int, input().split())
board = [list(input().strip()) for _ in range(n)]

• 보드의 크기 n, m을 입력받음
• board라는 2차원 리스트에 보드 상태를 저장

 

 

 

 

2️⃣ Step 2: 동전 위치 찾기

def find_coins():
    coins = []
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'o':
                coins.append((i, j))
    return coins

• 보드를 모두 돌면서 o가 있는 좌표를 찾아 리스트로 반환
• 결과적으로 coins = [(x1, y1), (x2, y2)] 형태로 동전 2개의 위치를 얻음

 

 

 

 

3️⃣ Step 3: 좌표가 보드 안에 있는지 확인

def in_bound(x, y):
    return 0 <= x < n and 0 <= y < m

• (x, y) 좌표가 보드 안에 있는지 확인

 

 

 

 

4️⃣ Step 4: BFS 

 

 

1) 방향 정의

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

• 위, 아래, 왼쪽, 오른쪽 4방향 정의

 

 

 

2) 큐, 방문 배열 준비

q = deque()
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]

• q: BFS를 위한 큐
• visited[x1][y1][x2][y2]: 동전 1과 동전2가 각각 (x1, y1), (x2, y2)에 있을 때 방문했는지를 저장

 

 

 

3) 초기 상태를 큐에 넣기

x1, y1 = coins[0]
x2, y2 = coins[1]
q.append((x1, y1, x2, y2, 0))
visited[x1][y1][x2][y2] = True

• 동전 2개의 초기 위치와 이동 횟수를 큐에 넣음

 

 

 

4) BFS 시작

while q:
    x1, y1, x2, y2, cnt = q.popleft()

• 큐에서 현재 상태를 꺼냄

 

 

 

5) 이동 횟수 제한 검사

if cnt >= 10:
    break

• 버튼을 10번 이상 눌렀으면 더 이상 탐색하지 않고 종료함

 

 

 

6) 4방향으로 이동 시도

# directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dx, dy in directions:

• 4개의 방향(위, 아래, 왼쪽, 오른쪽)에 대해 각각 이동을 시도함

 

 

 

7) 동전 이동 및 보드 밖인지 검사

nx1, ny1 = x1 + dx, y1 + dy
nx2, ny2 = x2 + dx, y2 + dy

fall1 = not in_bound(nx1, ny1)
fall2 = not in_bound(nx2, ny2)

• 두 동전을 각각 움직여보고 이동한 결과가 보드 밖이면 fall1, fall2가 True가 됨

 

 

 

8) 보드 밖인 경우 처리

if fall1 and not fall2:
    return cnt + 1
if fall2 and not fall1:
    return cnt + 1
if fall1 and fall2:
    continue

• 하나만 떨어졌다면 버튼 누른 횟수에 +1을 하여 반환
• 둘 다 떨어졌다면 다음으로 넘어감

 

 

 

9) 벽 충돌 처리

if not fall1 and board[nx1][ny1] == "#":
    nx1, ny1 = x1, y1
if not fall2 and board[nx2][ny2] == "#":
    nx2, ny2 = x2, y2

• 벽이 있다면 이동하지 않고 원래 자리로 돌아옴

 

 

 

10) 방문하지 않은 경우 처리

if not visited[nx1][ny1][nx2][ny2]:
    visited[nx1][ny1][nx2][ny2] = True
    q.append((nx1, ny1, nx2, ny2, cnt+1))

• 아직 방문하지 않은 상태라면 방문 표시를 하고 큐에 추가함
• 이동 횟수도 +1을 하여 저장함

 

 

 

 

 

전체 코드

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


def find_coins():
    coins = []
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'o':
                coins.append((i, j))
    return coins

def in_bound(x, y):
    return 0 <= x < n and 0 <= y < m

def bfs():
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    q = deque()
    visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]

    x1, y1 = coins[0]
    x2, y2 = coins[1]
    q.append((x1, y1, x2, y2, 0))
    visited[x1][y1][x2][y2] = True

    while q:
        x1, y1, x2, y2, cnt = q.popleft()

        if cnt >= 10:
            break

        for dx, dy in directions:
            nx1, ny1 = x1 + dx, y1 + dy
            nx2, ny2 = x2 + dx, y2 + dy

            fall1 = not in_bound(nx1, ny1)
            fall2 = not in_bound(nx2, ny2)

            if fall1 and not fall2:
                return cnt + 1
            if fall2 and not fall1:
                return cnt + 1
            if fall1 and fall2:
                continue

            if not fall1 and board[nx1][ny1] == "#":
                nx1, ny1 = x1, y1
            if not fall2 and board[nx2][ny2] == "#":
                nx2, ny2 = x2, y2

            if not visited[nx1][ny1][nx2][ny2]:
                visited[nx1][ny1][nx2][ny2] = True
                q.append((nx1, ny1, nx2, ny2, cnt+1))
    return -1


# 입력 처리
n, m = map(int, input().split())
board = [list(input().strip()) for _ in range(n)]

# 초기 동전 위치 찾기
coins = find_coins()

# 최소 횟수 구하기
print(bfs())

Algorithm/백준/Gold/16197. 두 동전 at main · kuun1000/Algorithm