Baekjoon 17244 아맞다우산 JAVA

https://www.acmicpc.net/problem/17244

17244번: 아맞다우산

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2017244

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 전에 풀었던 백준 1194 달이 차오른다, 가자. 문제랑 비슷한 문제다.

https://blog.naver.com/soonil0119/222521105430

Baekjoon 1194 달이 차오른다, 가자. JAVA

map이 주어지는데 #은 벽 .은 이동 가능한 공간 X는 물건이며 물건을 모두 챙겨서

S에서 시작해서 E까지 몇 번 만에 가는지 구하는 문제다.

​

입력을 받아주면서 map에 X 값이 들어가 있으면 해당 값을 0, 1, 2...으로 바꿔준다.

이후 시작점 S는 큐에 삽입한 뒤 bfs를 진행한다.

​

이때 방문 배열을 3차원으로 만들어 두는데 마지막에 1<<5

즉 비트 마스킹을 이용해서 물건 들고 간 여부를 확인하여 준다.

​

최종적으로 bfs에서 빠져나오는 부분에서 현재 E 부분에

도착했고 key 값이 n.key == (1<<x-'0')-1 즉 물건이 4개면

(1<<5) - 1한값이 물건 4개를 모두 가진 값이 되기 때문에 해당 식을 이용하며,

추가적으로 현재 x 값을 char형으로 두었기 때문에 '0'을 빼주고, x 값은 입력받으면서

x++로 사용하였기 때문에 물건 개수보다 1 크기 때문에 그냥 계산하면 된다.

​