[백준] dfs - 2667번 단지번호붙이기 (Java)

문제링크

2667번: 단지번호붙이기

 

접근한 방법

• 연결되어있는 노드의 개수를 구하는 문제이므로
  dfs

 

---

풀이방법

1인 값이 상, 좌, 하, 우로 연결되어 있는 범위를 묶어 그 안의 있는 요소의 수를 세면된다.

1. 특정한 지점의 주변 상, 좌, 하, 우를 살펴본 뒤에 주변 지점 중에서 값이 1이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점 에서 다시 상, 좌, 하, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
   방문시마다 요소의 수를 더해준다.
3. 1~2번의 과정을 모든 노드에 반복

4. 묶여있는 범위마다의 요소의 값을 구한 후 그 값을 list에 넣어준다.

 

---

소스코드 작성 방법

• 맵의 크기(n), 각 단지의집 수(count)를 전역 필드로 선언한다.
• 단지의 정보(map), 방문 여부(visitied)를 전역 필드로 선언한다.
• 총 단지의 횟수(result)를 list 전역 필드로 선언한다.
• 방향 배열 dx, dy로 상 좌 하 우 움직임을 저장한다.
• dfs 메소드의 인자를 노드 번호(curR, curC)로 받는다.
  • vistied[curR][curC] = true로 하여 방문 처리
  • 방문할 때 마다 count++하여 집의 개수를 추가한다.
  • nextR, nextC를 for문 안에 선언하여 현재 위치에서 상 좌 하 우 위치를 탐색한다.
    • nextR은 curR + dx[dir]
      nextC는 curC + dx[dir] 로 상 좌 하 우 값을 선언해준다.
    • 상 좌 하 우 위치 이동 시 n*n배열의 크기보다 크면 continue하여 넘어간다.
    • map[nextR][nextC] = 1이고 (집이 있고) visited[nextR][nextC] = false로 아직 방문하지 않았다면
      dfs 메소드를 재귀적으로 호출하여 방문수행
• solution 메소드에서 1번 노드부터 마지막 번호 노드까지 탐색을 수행한다.
  * 방문하지 않은 노드만 방문 수행 !
  • 방문을 수행하기 전에 count = 0 으로 초기화하고,
    방문이 끝난 후에, list인 result에 add하여준다.

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.*;

public class Q_2667_AttachNumber_20210521 {
    public static int n;
    public static int[][] map;
    public static boolean[][] visited;
    // 상좌하우
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static int count;
    public static List<Integer> result = new ArrayList();
    public static void solution() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    count = 0;
                    dfs(i, j);
                    result.add(count);
                }
            }
        }

    }
    
    public static void dfs(int curR, int curC){
        // 방문 처리
        visited[curR][curC] = true;
        count ++;

        for (int dir = 0; dir < 4; dir++) {
            int nextR = curR + dx[dir];
            int nextC = curC + dy[dir];

            // 범위를 벗어나면 반복문 넘어가기
            if(nextR < 0 || nextC < 0 || nextR >= n || nextC >=n) continue;
            else if(map[nextR][nextC] == 1 && !visited[nextR][nextC]){
                dfs(nextR, nextC);
            }
        }
    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visited = new boolean[n][n];

        for(int i=0 ; i<n ; i++) {
            String temp = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = temp.charAt(j) - '0';
            }
        }

        solution();

        Collections.sort(result); // list 오름차순 정렬
        bw.write(result.size()+"\n");
        for (int i = 0; i < result.size(); i++) {
            bw.write(result.get(i)+"\n");
        }
        br.close();
        bw.close();
    }
}