[알고리즘 문제] 백준2667 - 단지번호붙이기

문제 자체는 쉽다. 표에서 1로 생성된 군집의 수와 각각의 군집내에서 1의 숫자를 출력하면 된다.

아이디어는 배열을 반복하면서 가다가 1을 찾으면 그떄부터 탐색을 시작하는데, 이때 dfs와 bfs를 사용하면 된다.

 

먼저 dfs로 구현을 했고, 이후에 bfs로도 같이 구현을 해보았다.

 

dfs : https://github.com/pyh0414/algorithm/blob/master/dfs/Q2667(dfs).java

bfs : https://github.com/pyh0414/algorithm/blob/master/dfs/Q2667(bfs).java

 

코드에서 좀 특별한 점은,

1. 배열을 선언할 때 N만큼 선언한 게 아니라, N+2만큼 선언

2. dfs,bfs함수를 실행하기 전에 1을 체크하고, 1을 검사하는 부분에는 x,y가 아니라 x+1,y+1을 사용

3. import java.awt.Point 사용

 

1,2 : 이렇게 하면 나중에 탐색을 할 때, 배열을 벗어나는지 검사하지 않아도 된다. 실제로 배열은 <그림 1>에서 0으로 한번 더 감싼 모양이 되기 때문이다. 그리고 탐색을 하면서 조건이 값이 1인 경우만 해당되기 때문에 가장자리를 탐색하는 경우가 없기 때문이다.

 

3: bfs에서 que에 x,y좌표를 저장하기 위해 클래스를 하나 만들었는데, 그 보다  import java.awt.Point를 사용하면 x,y값을 쉽게 관리할 수 있다.