백준: 16197 두 동전

문제

16197번: 두 동전

 

문제 풀이

 NxM 크기의 보드와 4개의 버튼으로 이루어진 게임에서 버튼을 클릭하여 하나의 동전을 보드 밖으로 보내는 문제이다. 버튼은 상, 하, 좌, 우로 2개의 동전을 동시에 움직이게 한다. 이때 최소로 버튼을 클릭하여 하나의 동전을 보드 밖으로 보내는 경우를 반환하는 문제이다.

 

 이 문제는 앞서 다룬, 구슬 탈출, 구슬 탈출 3와 상당히 유사한 문제이다. 이 문제를 풀 수 있는 로직을 기억한다면 해당 문제 역시 쉽게 풀 수 있다. 문제는 다음 로직과 같이 접근하면 답을 찾을 수 있다.

 

• BFS를 통해 탐색을 한다.
• 동전을 동시에 상, 하, 좌, 우 좌표 중 하나로 움직인다.
  • 시도 횟수가 10회 이상이라면 중단하고, -1을 반환한다.
  • 두 동전 모두 밖으로 떨어진다면, 탐색에서 제외한다.
  • 두 동전 중 하나만 밖으로 떨어진다면 답을 찾은 것이므로, 시도 횟수를 반환한다.
  • 동전이 벽과 만난다면, 현재의 경로를 유지한다.
  • 각 좌표의 경로를 방문하였는지 확인하고, 방문하지 않았다면 큐에 추가한다.

 

코드

from sys import stdin
from collections import deque


def search_coin():
    location = []
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'o':
                location.append([i, j])
    return location


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


def bfs(coins):
    q = deque([[coins[0], coins[1], 1]])
    visited[coins[0][X]][coins[0][Y]][coins[1][X]][coins[1][Y]] = True

    while q:
        one, two, cnt = q.popleft()

        # cnt가 10이 넘어도 찾지 못하면 찾을 수 없는 경우.
        if cnt > 10:
            break

        for dx, dy in dirs:
            # 각각의 동전을 이동 시킴.
            next_one = [one[X] + dx, one[Y] + dy]
            next_two = [two[X] + dx, two[Y] + dy]

            # 두 동전 모두, 방문 가능하지 않은 위치로 간다면 탐색하지 않아도 됨.
            if not visitable(*next_one) and not visitable(*next_two):
                continue

            # 동전1의 다음 위치가 밖이거나, 동전2의 다음 위치가 밖인 경우
            # 최소 버튼 클릭을 반환하고 종료.
            if visitable(*next_one) and not visitable(*next_two) or \
                    not visitable(*next_one) and visitable(*next_two):
                return cnt

            # 동전이 벽과 만난 경우, 현재 위치에서 고정.
            if graph[next_one[X]][next_one[Y]] == '#':
                next_one = one
            if graph[next_two[X]][next_two[Y]] == '#':
                next_two = two

            # 방문하지 않은 경우, 경로 탐색을 위해 큐에 추가함.
            if not visited[next_one[X]][next_one[Y]][next_two[X]][next_two[Y]]:
                visited[next_one[X]][next_one[Y]][next_two[X]][next_two[Y]] = True
                q.append([next_one, next_two, cnt + 1])
    return -1


if __name__ == '__main__':
    X, Y = 0, 1
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    n, m = map(int, stdin.readline().split())
    graph = [list(stdin.readline().rstrip()) for _ in range(n)]
    # 방문 상태를 동전 두개의 좌표에 따라 체크하기 위해 4차원 배열 선언.
    visited = \
        [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]

    print(bfs(search_coin()))