-
#17244 아맞다우산Code/BOJ 2020. 1. 3. 12:59728x90반응형
출처:https://www.acmicpc.net/problem/17244
17244번: 아맞다우산
경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등
www.acmicpc.net
위 그림과 같이 입력값이 주어져 S에서 출발하여 물건X를 모두 수집하고 E로 도착하기 위한 최단 경로를 구하는 문제이다. 비트마스킹을 이용하여 visit[x][y][key(보유 키 현황)]배열을 생성하였고 bfs를 통해 구현하였다.
예를 들어 보유한 키가 0번 1번이면 00001 | 00010 = 00011 이 키 보유 현황이 되고 이때의 visit에서 bfs를 통해 새로운 키나 목적지를 찾아가게 된다.
728x90반응형'Code > BOJ' 카테고리의 다른 글
#17836 공주님을 구해라! (0) 2020.01.05 #9328 열쇠 (0) 2020.01.05 #2096 내려가기 (0) 2020.01.02 #1917 정육면체 전개도 (0) 2020.01.02 #2098 외판원 순회 (0) 2020.01.01