그래프와 순회. [2667], [1012]

[1. 문제 설명]

NxN 크기의 배열에서 아래,위로 인접한 집들을 하나의 단지로 묶을 수 있을 때,

전체 단지의 개수와 각 단지에 속한 집들의 개수를 오름차순으로 출력

(대각선으로 인접한 것은 취급하지 않는다.)

 

 

 

[2. 풀이 접근]

인접한 집으로 이동 할 수 있다는 점에서

그래프 개념으로 접근할 수 있다.

 

어떤 위치에서 이동할 수 있는 방향은 상,하,좌,우 4가지가 되므로,

각 경우에 대해서 dfs 를 수행 해 볼수 있다.

 

그러나, 좌표를 움직여야 하므로,

좌표가 NxN 배열을 넘어 선 경우,

이미 방문한 좌표, 

좌표에 해당하는 값이 0인 경우는 무시해야 한다.

 

또한 작성 한 dfs 함수는 최종적으로 하나의 단지의 포함 된 집의 개수를 반환하는데,

기저 사례를 통과한 경우 최소 하나의 집이 있음이 보장된다.

 

따라서, 재귀 호출 한 결과 값만 return 할 값에 누적해주면 된다.

==> dfs 로 방문 할 위치를 재귀 호출 전 먼저 더해주는 오류가 있었음

==> ex) ret += (1+dfs(ny, nx)) 

==> 앞으로 방문할 ny, nx 에 대해서 1 이 중복되어 더해져 오답이 되버림.

 

 

 

[3. 코드]

 

[4. 1012 코드]

문제 2667 과 비슷함.