[백준] dfs - 2583번 영역 구하기 (Java)

문제링크

2583번: 영역 구하기

 

접근한 방법

• 연결 요소의 개수를 구하는 문제이므로
  dfs

 

---

풀이방법

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

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

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

 

• 여기서, 또 하나의 포인트는 입력이다.
  x y 좌표를 배열의 행과 열로 변환은 아래와 같은 수식으로 할 수 있다.
  

  

 

---

소스코드 작성 방법

• 맵의 크기(m,n), 좌표의 개수(k)를 전역 필드로 선언한다.
• 영역의 정보(map), 방문 여부(visitied)를 전역 필드로 선언한다.
• 각 영역의 의 개수(count)를 전역 필드로 선언한다.
• 영역의 개수(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.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Q_2583_CaculatingArea_20210523 {
    public static int m,n,k;
    public static int[][] map;
    public static boolean[][] visited;
    public static int count;
    // 상좌하우
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static List<Integer> list = new ArrayList<>();
    public static void solution() {
        for (int curR = 0; curR < m; curR++) {
            for (int curC = 0; curC < n; curC++) {
                if(map[curR][curC] == 0 && !visited[curR][curC]){
                    count = 0;
                    dfs(curR, curC);
                    list.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 >=m || nextC >=n) continue;
            else if(map[nextR][nextC]== 0 && !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));

        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        map = new int[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < k ; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            int r1 = m - y2;
            int r2 = m - y1 - 1;
            int c1 = x1;
            int c2 = x2 - 1;

            for (int r = r1; r <= r2; r++) {
                for (int c = c1; c <= c2; c++) {
                    map[r][c] = 1;
                }
            }
        }

        solution();
        Collections.sort(list);
        bw.write(list.size()+"\n");
        for (int i = 0; i < list.size(); i++) {
            bw.write(list.get(i) +" ");
        }

        br.close();
        bw.close();

    }
}