[백준] 16197 : 두 동전 / python

1. 문제 설명

16197번: 두 동전

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

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

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

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

 

입력

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

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o : 동전
• . : 빈 칸
• # : 벽

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

 

출력

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

 

2. 풀이 전 계획과 생각

입력

• N, M → 세로 크기, 가로 크기 (1 ≤ N, M ≤ 20)
• board → N * M 2차원 배열
  • o: 동전
  • .: 빈 칸
  • #: 벽
  ⇒ 동전의 위치를 따로 저장해두자.

 

구하고자 하는바

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

 

문제 접근

언제 최소로 떨어지는지 규칙이 없으니, 모든 경우를 다 따져보자. 그 중 최소를 구해준다.

위의 문제의 경우 두 동전 동시에 갈 때 dfs 탐색해서 동전이 간다. 동전들이 어떻게 가는지 정의를 해주자.

갈 때의 경우는 무엇이 있는가?

• 두 동전 둘다 범위에 벗어나면 : -1 → 종료
• 동전 하나만 범위에 벗어나면 : 버튼 횟수 → 종료
• 범위에 벗어나지 않는다면 : 다음 칸으로 dfs 탐색한다. (재귀 사용)
  • 탐색 할 때의 조건은 벽이 아닌 빈칸과 동전일 때만 탐색한다.

이외에도 종료 조건은?

10이 넘어가면 -1을 리턴한다.

 

3. 1차 풀이 - 백트레킹

N, M = tuple(map(int, input().split()))
grid = [ input().rstrip() for _ in range(N) ]
min_count = 11

def get_start_pos():
    coin_pos = []
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 'o':
                coin_pos.append((i, j))

    return coin_pos

def in_range(y, x):
    return 0 <= y < N and 0 <= x < M

def can_go(y, x):
    if 0 <= y < N and 0 <= x < M:
        return not grid[y][x] == '#'
    return True

def go(y1, x1, y2, x2, count):
    global min_count

    if not in_range(y1, x1) and not in_range(y2, x2):
        return
    elif not in_range(y1, x1) or not in_range(y2, x2):
        min_count = min(min_count, count)
        return

    if count > 10:
        return

    dys = [-1, 1, 0, 0]
    dxs = [0, 0, -1, 1]

    for dy, dx in zip(dys, dxs):
        ny1, nx1 = y1 + dy, x1 + dx
        ny2, nx2 = y2 + dy, x2 + dx
        if can_go(ny1, nx1) and can_go(ny2, nx2):

coin1_start_pos, coin2_start_pos = get_start_pos()
go(coin1_start_pos[0], coin1_start_pos[1], coin2_start_pos[0], coin2_start_pos[1], 0)

if min_count == 11:
    print(-1)
else:
    print(min_count)

 

문제점

test case 3번, 5번을 통과하지 못했다.

문제 조건을 잘못 이해했다.

동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.

이 조건을 둘 중에 하나라도 벽이 있으면 둘다 이동하지 않는 것으로 잘못 이해했다.

테스트케이스의 입력값에 따른 결과값을 보니

이 조건의 의미는 각 동전마다 벽이 있으면 이동하지 않으면 되고, 벽이 아니면 이동하면 된다.

 

4. 2차 풀이 - 백트레킹

N, M = tuple(map(int, input().split()))
grid = [ input().rstrip() for _ in range(N) ]
min_count = 11

def get_start_pos():
    coin_pos = []
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 'o':
                coin_pos.append((i, j))

    return coin_pos

def in_range(y, x):
    return 0 <= y < N and 0 <= x < M

def can_go(y, x):
    if 0 <= y < N and 0 <= x < M:
        return not grid[y][x] == '#'
    return True

def go(y1, x1, y2, x2, count):
    global min_count

    if not in_range(y1, x1) and not in_range(y2, x2):
        return
    elif not in_range(y1, x1) or not in_range(y2, x2):
        min_count = min(min_count, count)
        return

    if count > 10:
        return

    dys = [-1, 1, 0, 0]
    dxs = [0, 0, -1, 1]

    for dy, dx in zip(dys, dxs):
        ny1, nx1 = y1 + dy, x1 + dx
        ny2, nx2 = y2 + dy, x2 + dx
        if can_go(ny1, nx1) and can_go(ny2, nx2):
            go(ny1, nx1, ny2, nx2, count + 1)
        elif can_go(ny1, nx1):
            go(ny1, nx1, y2, x2, count + 1)
        elif can_go(ny2, nx2):
            go(y1, x1, ny2, nx2, count + 1)

coin1_start_pos, coin2_start_pos = get_start_pos()
go(coin1_start_pos[0], coin1_start_pos[1], coin2_start_pos[0], coin2_start_pos[1], 0)

if min_count == 11:
    print(-1)
else:
    print(min_count)

 

5. 다른 풀이 - BFS 탐색

위의 문제는 최소 몇번 눌러야 하는지를 구하므로 BFS 탐색으로 해결할 수가 있다.
10 이상은 움직일 필요가 없음으로, 최대 시간복잡도는 4^10이니, BFS로도 해결할 수 있다.
또한, 중복으로 이동이 가능하므로, 방문처리 할 필요가 없다.

from collections import deque

N, M = tuple(map(int, input().split()))
grid = [ input().rstrip() for _ in range(N) ]
min_count = 11

def get_start_pos():
    coin_pos = []
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 'o':
                coin_pos.append((i, j))

    return coin_pos

def in_range(y, x):
    return 0 <= y < N and 0 <= x < M

def can_go(y, x):
    if 0 <= y < N and 0 <= x < M:
        return not grid[y][x] == '#'
    return True

def bfs():
    global min_count

    bfs_queue = deque()
    y1, x1 = coin1_start_pos
    y2, x2 = coin2_start_pos
    bfs_queue.append((y1, x1, y2, x2, 0))

    dys = [-1, 1, 0, 0]
    dxs = [0, 0, -1, 1]

    while bfs_queue:
        y1, x1, y2, x2, count = bfs_queue.popleft()

        if count > 10:
            continue

        if not in_range(y1, x1) and not in_range(y2, x2):
            continue

        elif not in_range(y1, x1) or not in_range(y2, x2):
            min_count = min(min_count, count)
            continue

        for dy, dx in zip(dys, dxs):
            ny1, nx1 = y1 + dy, x1 + dx
            ny2, nx2 = y2 + dy, x2 + dx
            if can_go(ny1, nx1) and can_go(ny2, nx2):
                bfs_queue.append((ny1, nx1, ny2, nx2, count + 1))
            elif can_go(ny1, nx1):
                bfs_queue.append((ny1, nx1, y2, x2, count + 1))
            elif can_go(ny2, nx2):
                bfs_queue.append((y1, x1, ny2, nx2, count + 1))

coin1_start_pos, coin2_start_pos = get_start_pos()
bfs()

if min_count == 11:
    print(-1)
else:
    print(min_count)

 

아쉬운 점

위의 코드는 BFS탐색으로 해결이 가능했다.
그러나 최단 횟수를 지난 다른 횟수의 경우도 계속 큐에 넣어 비효율적인 부분이 있고 BFS 탐색의 특징을 살리지 못했다.

좀더 효율적으로 코드를 작성하기 위해,
시작점에서 가까운 점들부터 탐색하는 BFS의 특성을 살려 두 동전 중 하나가 떨어지면 바로 결과를 리턴할 수 있게 하자.

(BFS 탐색은 시작점에서 가까운 점들부터 탐색하기 때문에 최단 거리/시간/횟수를 보장한다.)

 

6. 다른 2차 풀이 - BFS 탐색 (좀 더 효율적으로)

from collections import deque

N, M = tuple(map(int, input().split()))
grid = [ input().rstrip() for _ in range(N) ]

def get_start_pos():
    coin_pos = []
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 'o':
                coin_pos.append((i, j))

    return coin_pos

def in_range(y, x):
    return 0 <= y < N and 0 <= x < M

def is_wall(y, x):
    return grid[y][x] == '#'

def bfs():
    bfs_queue = deque()
    y1, x1 = coin1_start_pos
    y2, x2 = coin2_start_pos
    bfs_queue.append((y1, x1, y2, x2, 0))

    dys = [-1, 1, 0, 0]
    dxs = [0, 0, -1, 1]

    while bfs_queue:
        y1, x1, y2, x2, count = bfs_queue.popleft()
        if count > 10:
            return -1

        for dy, dx in zip(dys, dxs):
            ny1, nx1 = y1 + dy, x1 + dx
            ny2, nx2 = y2 + dy, x2 + dx

            if in_range(ny1, nx1) and in_range(ny2, nx2):
                if is_wall(ny1, nx1):
                    ny1, nx1 = y1, x1
                if is_wall(ny2, nx2):
                    ny2, nx2 = y2, x2
                bfs_queue.append((ny1, nx1, ny2, nx2, count + 1))
            elif in_range(ny1, nx1):
                return count + 1
            elif in_range(ny2, nx2):
                return count + 1

coin1_start_pos, coin2_start_pos = get_start_pos()
print(bfs())

 

7. 풀이 후 알게된 개념과 소감

• 처음에 문제를 풀 때, 동전이 가는 경우가 너무 많아 어떻게 처리해줄까 고민이 들었는데,
  문제 조건에 맞게 갈 수 있는 경우를 나눠주고 그에 맞게 처리해주니 쉽게 풀렸었다.
• DFS 탐색이나 백트레킹으로 문제를 해결할 때 문제가 복잡하다고 느껴지면
  차근차근 문제에 맞게 갈 수 있는 경우를 적고 그에따라 처리해주자.
• 시작점에서 가까운 점들부터 탐색하는 BFS는 최단 거리/시간/횟수를 보장하며,
  효율적으로 최단 거리를 구할 수 있다.