백준 17244번 아맞다우산

문제 링크입니다: https://www.acmicpc.net/problem/17244

17244번: 아맞다우산

비트마스킹을 통해 아이템을 주웠는지 판별해야하는 흥미로운 BFS 문제였습니다.

물건 'X' 마다 각각 고유 인덱스를 부여하여 비트 연산을 통해 주웠는지를 판별하는 것이 핵심이였습니다.

물건은 최대 5개이기 때문에 인덱스는 최대 4이고 0 ~ 4 까지 모두 표시하기 위해서는 크기가 2^5 즉, 32인 배열이 필요합니다.

물건을 줍는 과정에서 같은 칸을 밟을 수 있기 때문에 평소처럼 이차원 visited 배열을 사용하면 안되고 어떤 물건을 주웠는가까지 표시하는 삼차원 visited 배열을 사용해야했습니다.

따라서, visited 배열을 visited[MAX][MAX][1 << MAX_STUFF] 로 표시했습니다.

 

BFS 탐색을 진행할 때는 다음 칸에 줍지 않은 물건 여부를 확인한 뒤

1. 줍지 않은 물건이 있다면 checked 변수에 비트 연산을 통해 주웠다고 표시하고 큐에 넣습니다.

2. 줍지 않은 물건이 없고 갈 수 있는 칸이라면 그대로 큐에 넣습니다.

3. 모든 물건을 주웠고 도착점에 도착한다면 time을 출력하고 프로그램을 종료합니다.

 

문제 조건에 모든 물건을 챙길 수 없는 경우는 주어지지 않는다. 라고 나와있기 때문에 해당 부분에 대해서는 예외처리를 하지 않았습니다.

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~