[Java] 백준 2667번 : 단지번호붙이기 <Silver 1>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

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

2667번: 단지번호붙이기

Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    int count = 0;
    int num = 0;
    ArrayList<Integer> number = new ArrayList<>();

    void run() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[][] graph = new int[N+2][N+2];

        for(int i = 1; i < N+1; i++){
            String input = bf.readLine();
            for(int j = 1; j < N+1; j++){
                graph[i][j] = Integer.parseInt(String.valueOf(input.charAt(j-1)));
            }
        }

        DFSUtil(graph);

    }

    void DFSUtil(int[][] graph){
        for(int i = 1; i < graph.length-1; i++){
            for(int j = 1; j < graph.length-1; j++){
                if(graph[i][j] == 1){
                    DFS(graph, i, j);
                    count++;
                    number.add(num);
                    num = 0;
                }
            }
        }
        System.out.println(count);
        Collections.sort(number);
        for(Integer n:number){
            System.out.println(n);
        }
    }

    void DFS(int[][] graph, int i, int j){
        num++;
        graph[i][j] = 2;
        if(graph[i+1][j] == 1){
            DFS(graph, i+1, j);
        }
        if(graph[i][j+1] == 1){
            DFS(graph, i, j+1);
        }
        if(graph[i-1][j] == 1){
            DFS(graph, i-1, j);
        }
        if(graph[i][j-1] == 1){
            DFS(graph, i, j-1);
        }
    }

    public static void main(String[] args) throws IOException {
        Main my = new Main();
        my.run();
    }
}

---

Code 필수 요소

1. Graph  탐색

2. 탐색 조건 설정

 

// Graph 탐색

이번 문제는 DFS를 사용했다.

DFS에 대한 설명은 아래 링크를 걸어 둘테니까 모른다면 거기서 확인해봐라. 

 

// 탐색 조건 설정

내가 작성한 조건은 이렇다.

1. 그래프의 모든 숫자를 탐색하며 숫자 1을 발견한다.

2. 발견한 위치의 상하좌우 숫자를 탐색하며 존재할 경우 해당 위치로 DFS를 진행시킨다.

3. 탐색이 종료되었을 경우 count++을 해주어 단지의 갯수를 세주고, 그래프의 다음숫자를 탐색하며 위 과정 반복

 

// 전체적 설명

대부분의 사람들은 조건을 넣어줘서 그래프의 끝부분에 있을때 범위를 넘어가지 않도록 탐색을 한다.

그래서 나는 오히려 그래프를 한칸씩 더 만들어줘서 테두리를 0으로 한바퀴 둘러줬다. 그러고 한칸씩 안으로 들어와서 탐색을 하기 시작한다면, 조건 없이도 끝부분이 0이기때문에 결과에 영향을 주지않고 탐색할 수 있다. 그래서 그래프를 만들때 +2를 한 이유다.

 

그리고 각 단지가 몇칸인지는 num변수를 활용해서 DFS를 호출할때마다 ++시켜줬고, 해당 값을 ArrayList에 넣어줘서 기록했다. 그 후 리스트를 오름차순 정렬 시킨 후 출력하는 방식으로 문제를 해결했다. 

 

 

DFS와 BFS란?

https://naemamdaelo.tistory.com/37

알고리즘 - 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

사실상 DFS나 BFS를 쓸줄 안다면 약간의 활용 정도였다. 약간 고민하면 풀린 정도.

물론 문제를 잘 읽자... 정렬 안해놓고 왜 자꾸 틀렸다고 뜨지 한참 고민했따..

 

-꿑-