[백준/파이썬] 17244. 아맞다우산

[Gold II] 아맞다우산 - 17244

문제 링크

성능 요약

메모리: 115380 KB, 시간: 124 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 비트마스킹, 격자 그래프

제출 일자

2025년 11월 24일 20:21:14

문제 설명

경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다.

"아 맞다 우산!!!"

경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다.

외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.

평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다.

경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.

경재 씨를 위해 집을 위에서 바라본 모습과 챙겨야 할 물건들의 위치들을 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.

입력

첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)

두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.

비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.

챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.

출력

S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력한다. 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.

 

from collections import deque

di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

def bfs(si:int, sj:int, ei:int, ej:int, cnt:int) -> int :
    q = deque()
    q.append((si, sj, 0))   # si, sj, 물건 갯수
    v[si][sj][0] = 0

    while q :
        ci, cj, bit = q.popleft()
        curr = v[ci][cj][bit]

        if (ci, cj) == (ei, ej) and bit == 2 ** cnt - 1:
            return curr

        for d in range(4) :
            ni, nj = ci + di[d], cj + dj[d]
            if 0 <= ni < M and 0 <= nj < N and v[ni][nj][bit] == -1 :
                if arr[ni][nj] == "#" :
                    continue
                elif arr[ni][nj] == "X" :
                    nxt_bit = bit | (1<<tbl[(ni, nj)])
                    q.append((ni, nj, nxt_bit))
                    v[ni][nj][nxt_bit] = curr + 1
                else :
                    q.append((ni, nj, bit))
                    v[ni][nj][bit] = curr + 1

    return -1

def main() :
    global N, M, arr, v, tbl
    N, M = map(int, input().split())
    arr = [list(input().rstrip()) for _ in range(M)]
    cnt = 0
    si = sj = ei = ej = 0
    tbl = {}    # 중복 처리를 위해 물건 위치를 담자.
    for i in range(M) :
        for j in range(N) :
            if arr[i][j] == "S" :
                si, sj = i, j
                arr[si][sj] = "."
            elif arr[i][j] == "E" :
                ei, ej = i, j
            elif arr[i][j] == "X" :
                tbl[(i, j)] = cnt
                cnt += 1

    v = [[[-1 for _ in range(1<<cnt)] for _ in range(N)] for _ in range(M)]

    print(bfs(si, sj, ei, ej, cnt))

if __name__ == "__main__" :
    main()

이 문제도 사실 오랜만에 풀어보는데 테이블을 만드는 것에서 막혀서 기존 답안을 확인하였다. 중복 방지를 꼼꼼하게 해야하는 게 이 문제의 포인트. 함수별로 살펴보자

MAIN 함수

• global N, M, arr, v, tbl 을 넣어 글로벌 변수로 지정한다. 
• cnt : 물건 갯수 체크
• si, sj, ei, ej : 시작 좌표와 종료 좌표를 받아올 변수 초기화
• tbl : 여기는 물건들의 좌표를 체크할 테이블을 딕셔너리로 생성. => 여기서 많이 헤맸다.
• 이중 반복문을 통하여 시작좌표, 종료좌표, 물건좌표를 받아온다.
  • 시작좌표 : 시작좌표(si, sj) 를 받고나서 "S"를 "."으로 바꿔준다. 사실 코드상 안바꿔줘도 잘 돌아가는데 다른 문제에서 이것과 관련된 문제가 발생했던 것으로 기억하기 때문에 실수 줄이는 겸 바꿔주었다.
  • 종료좌표 : 종료좌표(ei, ej)를 받아온다.
  • 물건좌표 : 딕셔너리 키-밸류를 물건좌표-물건 갯수 로 하여 딕셔너리에 입력한다. 
• v : 방문 배열. [열][행][지금 소지하고 있는 물건 갯수] 를 집어 넣어야 되기 때문에 다음과 같이 설정하였다. 그리고 초기값은 0부터 시작해야 하기 때문에 -1로 설정.
• 그럼 각 좌표들과 물건 갯수로 BFS 탐색을 실시. 

BFS 함수

• 이전에 상하좌우 이동 좌표를 만들어 놓고 시작하자. 실수 줄이기용
• q를 생성하고 초기값 (si, sj, 들고 있는 물건 개수 = 0)을 입력
• v 배열에 초기좌표 방문 처리. 초기값 -1로 되어있기 때문에 0으로 초기화
• BFS 탐색 시작
  • 현재 좌표들과 현재 들고 있는 물건 갯수를 받아옴.
  • 정답처리 : 현재 위치 == 종료 위치 그리고 현재 물건을 다 들고 있는지 체크
  • 정답이라면, 현재 걸음걸이를 반환한다. 
  • BFS 조건 (네방향, 범위내, 미방문, 각 조건들)들을 확인한다. 
    • "#" : 벽이기 때문에 지나간다. 
    • "X" : 물건이 있는 위치. 이때  물건이 있는 위치가 bit와 비교하였을 때 일치하는지 체크. 추후 상세 설명
    • "." : 걸음걸이 + 1 을 한 후 큐에 삽입.
• 만일 도달하지 못한다면 -1을 반환한다. 여기서는 디버깅 활용면에서 될 것 같다. 

비트마스킹을 활용하여 해결하는 문제였다. 조건을 잘 파악하자.