[BOJ] 백준 27211 도넛 행성 (JAVA)

BFS + 모듈러!

📑 문제

백준 27211 도넛 행성

---

🌱 아이디어

BFS탐색을 통해 맵밖으로 나가게 된 경우를 모듈러 연산으로 처리하자!

 

만약 도넛행성에 있다고 상상해 보자! 어떤 방향으로 쭉 직진하게 되었을 때 결국 제자리로 돌아올 것이다.

즉 좌표  xy (0,0)에서 한 칸 더 위로 직진한다면 (0, N-1)이 되어야 한다. 이 조건은 동서남북 어디서나 동일하게 적용한다.

 

위 문제는 기존에 범위체크에서 배열밖 좌표로 이동하는 것을 막아주는 BFS가 아닌

맵밖으로 나간다면 반대 방향으로 탐색하게 만들어야 한다.

 

모듈러 연산을 통해 위와 같은 효과를 얻을 수 있다.

 

예를 들어 N = 5 일 때

 

배열의 인덱스는 0, 1, 2, 3, 4 일 것이다

 

인덱스 5를 탐색하려고 할 때 5 %= N을 통해 다시 인덱스 0을 탐색하게 만들면 된다.

---

🌱 코드 및 풀이

위 문제는 탐험할 수 있는 구역의 개수를 구해야 한다. 방문처리가 되지 않았다면 cnt++하고 이어진 공간을 탐색하며

방문처리하자.

---

🌱 느낀 점

 

개인적으로 신선한 문제였다 BFS문제에서 범위체크를 이렇게 응용하는 문제를 처음 풀어본다ㅎㅎ

경곗값처리만 고민하면 쉽게 풀 수 있다!