[백준 | Java] 2667번 단지번호붙이기

2667번 / 단지번호붙이기

❓ 단지번호붙이기

🏷️ 관련 주제 : DFS

💦 나의 시도

Try. DFS

1. 지도의 크기 N을 BufferedReader로 입력 받아 int형으로 변환 후, int N을 초기화
2. N x N 지도 map을 이차원 int 배열로 선언
3. 각 집을 탐색할 때, 이미 탐색한 집을 체크할 이차원 boolean 배열 visited 초기화
4. 0 ~ (N - 1) 범위를 이중 for문으로 돌기
   • 집의 유무를 나타내는 값 int house를 br.read() - '0'로 초기화
   • map[i][j]에 house를 할당
   • house가 0이면 visited에 true를 할당
   • 안쪽 for문이 끝날 때, br.readLine()을 실행하여 줄바꿈 공백 처리
5. 단지내 집 수를 담을 ArrayList houseCntArray를 초기화
6. 단지내 집 수를 체크할 함수 checkHouse(int r, int c) 정의
   • r, c가 배열의 범위를 벗어나면 0을 반환
   • map[r][c]가 이미 탐색한 범위이면(visited[r][c] == true) 0을 반환
   • 여기 코드까지 실행했다면 탐색하지 않은 집이므로 visited[r][c]에 true를 할당
   • 여기 코드까지 실행했다면 이 탐색 범위에는 집이 존재하므로 현재 위치의 값은 1이고 주변의 집도 탐색해야함.
     • 재귀함수를 이용하여 결괏값을 반환 
     • map[r][c] + checkHouse(r - 1, c) + checkHouse(r, c - 1) + checkHouse(r, c + 1) + checkHouse(r + 1, c)
7. 0 ~ (N - 1) 범위를 이중 for문을 돌면서 단지 내 집의 수를 탐색
   • 이미 탐색한 집이면(visited[i][j] == true) 반복문 처음으로 돌아감(continue;)
   • 그렇지 않으면 checkHouse()메서드로 단지 내 집 수 탐색 및 그 결괏값을 houseCntArray에 추가
8. 이중 for문이 끝나면 houseCntArray의 크기를 출력
9. Stream API를 이용하여 houseCntArray 정렬 및 각 원소를 출력

맞았습니다!!

• 메모리 : 14256 KB
• 시간 : 116 ms
• 코드 길이 : 1704 B

📑제출 기록 및 오답 원인

문제는 한번에 맞았는데 풀이를 정리하다보니 불필요한 코드들이 보여서 몇번 더 제출해서 제출이 3번임.
그래도 불필요한 코드를 제거해서 그런지 메모리와 시간이 아주 약간 좋아짐^^

💯 해결 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    public static int N;
    public static int[][] map;
    public static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int house = br.read() - '0';
                map[i][j] = house;

                if (house == 0) {
                    visited[i][j] = true;
                }
            }
            br.readLine();
        }

        ArrayList<Integer> houseCntArray = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i][j]) {
                    continue;
                }

                houseCntArray.add(checkHouse(i, j));
            }
        }

        System.out.println(houseCntArray.size());
        houseCntArray.stream().sorted().forEach(n -> System.out.println(n));
    }

    public static int checkHouse(int r, int c){
        if (r < 0 || c < 0 || r >= N || c >= N) {
            return 0;
        }

        if (visited[r][c]) {
            return 0;
        }

        visited[r][c] = true;

        return map[r][c]
                    + checkHouse(r - 1, c)
                    + checkHouse(r, c - 1)
                    + checkHouse(r, c + 1)
                    + checkHouse(r + 1, c);
    }
}