[파이썬] 백준 17244 : 아맞다우산 (골드2)

[파이썬] 백준 17244 : 아맞다우산 (골드2)

17244번: 아맞다우산

---

문제

---

풀이

0. 방향성 생각

기본적으로 DP에서 하던거처럼 상태를 나눈다. 물건의 개수가 늘어갈수록 상대가 2배로 늘어나니

bitmask를 통해서 간편하게 처리한다는게 아이디어

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

w,h = map(int,input().split())
arr = [list(input()) for _ in range(h)]
table,count = {},0

for i in range(h):
    for j in range(w):
        if arr[i][j] == 'S':
            arr[i][j] = '.'
            start = (j,i)
        if arr[i][j] == 'X':
            table[(j,i)] = count
            count += 1

입력을 다 받고나서 시작점 start를 저장한다.

물건의 위치는 table에 저장하고 몇 개인지 카운트한다.

2. visit 초기화

step = [[1,-1,0,0],[0,0,1,-1]]
x,y = start
visit = [[[-1]*w for _ in range(h)] for _ in range(1<<count)]
visit[0][y][x] = 0
q = deque([(x,y,0)])

visit[상태][열][행] 순서대로 시작.

큐에는 x,y좌표와 아무것도 찾지 않은 상태인 0을 넣어준다.

 

3. 그래프 탐색

while q:
    x,y,bit = q.popleft()
    
    for i in range(4):
        
        nx = x + step[0][i]
        ny = y + step[1][i]

        if 0<=nx<w and 0<=ny<h and visit[bit][ny][nx] == -1 and arr[ny][nx] != '#':
            if arr[ny][nx] == 'X' :
                nbit = bit | 1<<table[(nx,ny)]
                visit[nbit][ny][nx] = visit[bit][y][x] + 1
                q.append((nx,ny,nbit))
                
            else:
                nbit = bit
                visit[bit][ny][nx] = visit[bit][y][x] + 1
                q.append((nx,ny,nbit))
                
            if arr[ny][nx] == 'E' and nbit == 2**count-1 :
                print(visit[nbit][ny][nx])
                break

X를 찾으면 상태가 변한다. table에서 물건마다 부여한 번호만큼 shift한 후 방문처리를 OR 연산으로 해준다.

'X'가 아닌 경우에는 상태가 변하지 않으므로 

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

w,h = map(int,input().split())
arr = [list(input()) for _ in range(h)]
table,count = {},0

for i in range(h):
    for j in range(w):
        if arr[i][j] == 'S':
            arr[i][j] = '.'
            start = (j,i)
        if arr[i][j] == 'E':
            end = (j,i)
        if arr[i][j] == 'X':
            table[(j,i)] = count
            count += 1

step = [[1,-1,0,0],[0,0,1,-1]]
x,y = start
visit = [[[-1]*w for _ in range(h)] for _ in range(1<<count)]
visit[0][y][x] = 0
q = deque([(x,y,0)])

while q:
    x,y,bit = q.popleft()
    
    for i in range(4):
        
        nx = x + step[0][i]
        ny = y + step[1][i]

        if 0<=nx<w and 0<=ny<h and visit[bit][ny][nx] == -1 and arr[ny][nx] != '#':
            if arr[ny][nx] == 'X' :
                nbit = bit | 1<<table[(nx,ny)]
                visit[nbit][ny][nx] = visit[bit][y][x] + 1
                q.append((nx,ny,nbit))
                
            else:
                nbit = bit
                visit[bit][ny][nx] = visit[bit][y][x] + 1
                q.append((nx,ny,nbit))
                
            if arr[ny][nx] == 'E' and nbit == 2**count-1 :
                print(visit[nbit][ny][nx])
                break

 

코멘트

DP에서 하던 발상이랑 비슷해서 첫 비트마스크 풀이인데도 나쁘지 않게 푼 듯.

많은 상태도를 bit연산으로 처리하는거 이외의 발상은 똑같다.