https://www.acmicpc.net/problem/17244
17244번: 아맞다우산
경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출
www.acmicpc.net
Problem
- 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!"
- 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.
- 경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.
- 경재 씨를 위해 집을 위에서 바라본 모습과 챙겨야 할 물건들의 위치들을 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.
조건
- 첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)
- 두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.
- 비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.
- 챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.
SOL
굉장히 쉬워보였는데, 재방문 여부 때문에, 어려웠던 문제이다. Troblue Shooting 된 부분을 보겠음!
예제에서 첫번째 줄만 봐도, 바로 통상적인 BFS만 쓰면 문제가 발생한다는걸 바로 느낄 수 있다.
주황색 부분에서 -> 하늘색 부분으로 간다고 생각해보자.
첫번째 문제점. 재방문을 처리해줄 수가 없다.
- 주황색을 들렸다가 -> 하늘색을 들리고 -> 어쩔 수 없이 다시 주황색을 들려야한다.(재방문이 일어난다)
- 하지만, 주황색을 재방문하는 경우는 2가지를 생각해줄 수 있게 된다.
- 주황색을 줍고 -> 하늘색을 줍고 -> 재방문 하는 경우 (O) => 우리가 원하는 경우
- 주황색을 줍고 -> 한칸 갔다가 -> 다시 주황색을 재방문하는 경우 (X) => 우리가 원하지 않는 경우
- 이때, 통상적인 방문체크대로 하면, 하늘색에서 주황색으로 돌아올 수 없게 된다.(방문했던 곳은 재방문을 하지 않기 때문에) ,그리고 지금은 일직선이라서 그렇지, 주황색 ->하늘색이 최소일 수도 있고, 하늘색 ->주황색이 최소일 수도 있다.
- 결론적으로, "S"를 기준으로 가장 가까이 있는 거리로, "X"들을 줍겠지만, 재방문이 일어날 시에, 그 거리들의 합은 최소거리가 아니게 될 뿐더러, 다 못줍는 경우도 생기게 되는게 문제이다.
두번째 문제점. "X"가 있는 곳에서 이전 상태의 정보를 알아야한다.
- 그리고, 또 문제점이 내가 "X"가 있는 곳에서 그 이전 상태의 정보가 하나도 반영이 되지 않는다는게 문제다.
- 통상적인 BFS를 쓰게 된다면, "S"를 기준으로 최단거리에 있을 뿐, 내가 파랑 -> 빨강 ->분홍 ->주황 등 어떤 공을 주웠는지에 대한 정보가 하나도 담겨있지 않게 된다. 그래서, 주운 갯수의 정보로 코드를 구현하게 되어도, 각각 위치가 다르기 때문에, 의미가 없게 된다.
- 즉, 모든 "X"들을 구분지을 필요가 있어졌고, "X"들이 내가 현재 주운 상태인지 아닌지를 확인할 방법이 필요하게 된다. 사실 이 부분의 아이디어는 내가 공부하지 못했던, "비트 마스킹"이라는 개념을 활용하게 되었다.
- 간단하게, 비트마스킹은, 비트로 내 상태를 저장하게 되는 개념인데, 위처럼 어떤 연속적인 상태를 저장해야할 때, 저장공간을 규칙적(논리적)으로 만드는 개념이다.
- 파랑공 : 1 , 빨강공 : 2, 분홍공 :3 주황공 :4 이라고 할때, 0000으로 치환해서,파랑공을 주웠으면, 0001,빨강공을 주웠으면 ,0010, 분홍공을 주웠으면 0100, 주황공을 주웠으면 1000 이라고 가정하고, 1111이 되면 다 주웠다고 생각을 하면된다. (사실 비트가 아니라, 파랑,빨강,분홍,주황에 숫자를 부여하고, 1234가 되었을때 처럼 숫자로 생각해줘도 상관은 없다)
- 1<<공들의 숫자로 하게 되면, 이제부터 우리는 어떤 공을 주웠는지, 줍지않았는지에 대한 정보를 알 수 있게 된다.
정리
우리가 원하는 것만 걸러주기 위해서, 어떻게 비트마스킹을 응용하면 되나면, visited배열에 주운 정보를 3차원으로 저장해주면 된다!
그 공을 주운자리로 또 되돌아가면 안되기 때문에, 주운상태에서는 , 새로운 방문배열이 생기는 것처럼 생각해주면 된다! (사실 처음에 이걸 만들어 주려다가, "X"를 방문할 때마다, 방문배열을 새로 만들어주니까, 그 이전 정보들이 날아가게 되서, 왔던 곳을 다시 방문하게되는 불상사가 일어나게 되버렸다)
- 주황색을 줍고 -> 하늘색을 줍고 -> 재방문 하는 경우 (O) => 우리가 원하는 경우
- 주황색을 줍고 -> 한칸 갔다가 -> 다시 주황색을 재방문하는 경우 (X) => 우리가 원하지 않는 경우
그래서, 공들의 번호를 그냥 발견되는 차례대로 0~n-1번까지 붙이고, "X"를 방문할 때마다, bit 정보랑 |연산을 계속해주면서, 탈출지점에 도달 했을 때, 공을 모두 주운 상태라면, 그 중에 최소 거리를 반영해주면 된다.
# 아 맞다! 우산!
# 비트 마스킹
import sys
from collections import deque
input= sys.stdin.readline
M,N =map(int,input().split())
board=[]
#visited[y][x][bit]
#11111(5개)는 32이므로, 32 까지해줘도됨.
visited=[[[0 for _ in range(35)] for _ in range(M)] for _ in range(N)]
dy=[0,1,0,-1]
dx=[1,0,-1,0]
sy,sx=0,0
#공 번호 저장
pos_X=[]
ans=sys.maxsize
for i in range(N):
tmp=input().rstrip()
for j in range(M):
if tmp[j]=="S":
sy,sx=i,j
elif tmp[j]=="X":
pos_X.append((i,j))
board.append(tmp)
def solve(y,x):
global ans
dq=deque()
dq.append((y,x,0,0))
visited[y][x][0] =1
while dq:
y,x,bit,d=dq.popleft()
# d가 현재 최솟값보다 크다면, 굳이 이 과정을 해줄 필요가 없다.
if d<ans:
for k in range(4):
ny=y+dy[k]
nx=x+dx[k]
if 0<=ny<N and 0<=nx<M and not visited[ny][nx][bit]:
visited[ny][nx][bit] = 1
nd=d+1
if board[ny][nx] !="#":
# 탈출점에 도달하고, 모든 공을 주운 상태일 때
if board[ny][nx]=="E"and bit+1 == 1<< len(pos_X):
ans=min(ans,nd)
# X를 만나면, 주운상태를 반영
elif board[ny][nx]=="X":
number_x=pos_X.index((ny,nx))
nbit= bit | (1<<number_x)
#print("number_X:",number_x)
#print("nbit",nbit)
visited[ny][nx][nbit] = 1
dq.append((ny,nx,nbit,nd))
# "."인 경우
else:
dq.append((ny,nx,bit,nd))
solve(sy,sx)
print(ans)'알고리즘 문제(SOL)' 카테고리의 다른 글
| [백준/12738/파이썬] 가장 긴 증가하는 부분수열 3 (0) | 2022.02.18 |
|---|---|
| [백준/16637/파이썬] 괄호 추가하기 (2) | 2022.02.17 |
| [백준/15686/파이썬] 치킨 배달 (0) | 2022.02.16 |
| [백준/16934/파이썬] 숫자 재배치 (0) | 2022.02.16 |
| [백준/14890/파이썬] 경사로 (0) | 2022.02.16 |