백준 - 인구 이동

문제 출처:www.acmicpc.net/problem/16234

16234번: 인구 이동

연합을 이루는 값들을 일치시켜주는 방식으로 인해 의외로 오래 걸린 문제다.

(1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100) 입력의 범위를 본 순간 DFS 보다는 BFS가 좀 더 수월할 거란 생각이 들었다.

 

내가 짠 코드 로직은 이거다.

1. while(true)문을 실행한다.

2. while문안에 이중for문으로 2차원 배열을 탐색한다.

3. 아직 방문안한 좌표면 방문 체크하고 더 이동할 수 있는지 파악

    3-1. 만약 더 이상 이동 못하면 해당 좌표는 방문을 해지

    3-2 더 이동 가능하면 wall이란 Queue에 각 좌표들을 저장, 그리고 flag변수 ++

        3-2-1 wall에 담긴 좌표를 기준으로 배열의 값들을 변환한다.

4. 만약 flag 변수가 0보다 크면 인구 이동이 발생했다는 것을 의미, flag=0이면 인구이동이 발생하지 않았다.

 

의외로 계속 틀린 이유는,  새로운 값으로 대치하는 방식을 방문했던 곳 기준으로 했기 때문이다.

그럴 경우 이전에 탐색했던 공간 또한 값을 바꾸게 되므로 틀린 결과가 나오게 된다(신기하게 Test Case는 다 맞았다..)