BFS. [14502]

[1. 문제 설명]

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

---

[2. 풀이 접근]

그래프 순회가 필요한 이유

• 이차원 배열에서 바이러스가 퍼져나간다.
• BFS 를 통해 이러한 과정을 모델링 할 수 있다.

완전 탐색

• 지도의 최대 크기는 8x8 이며, 여기서 반드시 벽을 놓을 위치 세곳을 정해야 한다.
• 전체 경우의 수는 ₆₄C₃  으로 대략 41,664 로 현실적인 경우의 수 인 것을 알 수 있다.
  => 현실적인 경우의 수 라면, 완전 탐색이 가장 안전한 풀이가 가능하다.

중복문제

• 벽을 놓을 위치를 정하는 것은 재귀 함수로 구현 할 수 있다.
• 문제는 벽을 놓을 때, 중복으로 놓은 경우를 막아야 한다는 것이다.
• 보통 중복으로 세는 경우를 방지하기 위해서는 항상 특정 형태로 답을 세는 것이다.
  => 사전 순으로 가장 먼저오는 답 하나만을 세거나
  => 2차원 배열에서 가장 윗 줄, 그 중에서도 가장 왼쪽부터 세는 것이다.
• 여기서 구현 시 실수한 부분은 아래와 같다.
  => y, x 위치에서 벽을 설치, 다음 벽 설치는 반드시 y=y`, x=x` 에서 시작하도록 한다.
  => 여기서 x`=1 이면, y 가 y=y`+1 에서 시작하더라도,
        x=1 로 고정 되기 때문에, y=y`+1, x=0 인 경우를 확인 할 수 없다.
• 단, y=y` 은 필요하다. 
  => 첫번째 벽을 y=1 에 설치한 경우, 두번째 벽은 y=0 에 설치 할 필요는 없기 때문이다.
  => 이 경우는 첫번째 벽을 y=0 에 설치한 경우와 같기 때문이다.

중복 문제 해결 2

• row 와 column 을 재귀 호출 시 전달
• 이 값을 그대로 사용
• 하지만, 다음 row 로 이동할 때, column 을 0 으로 초기화.

---

[3. 코드]