<baekjoon> 성곽

풀이

이 문제는 BFS탐색과 비트마스킹을 실행해줘야하는 문제다.

1. bfs탐색을 돌면서벽이 아닌 경우를 체크하고 방을 움직여야한다. 그럴 수 있는 조건은(move & (1 << k)) == 0)이다.

연산을 통해 해당 비트가 0이면 그 방향으로는 벽이 없고 뚤려있다는 것을 의미하므로 이동이 가능하다.

2. bfs를 한번돌때마다 방의 개수를 구할 수 있다.

3. bfs내에서 칸을 옮길때마다 roomChk변수를 ++해준다. bfs가 한번끝날때마다 기존의 room2변수랑 비교하여 더 크면 room2변수에 더 큰값을 넣어주고 roomChk변수는 초기화해준다.

4. 그 이후에는 벽을 부수고 이동하여 최대로 큰 방의 크기를 구하여야한다. 

5. (map[i][j] & bit) != 0) 일경우는 벽일 경우일때다 즉, 벽이면 그 벽을 부수고 이동하여 BFS탐색을 실시한다. 그리고 bfs가 끝났을 때 다시 벽을 복구해준다.

 

코드