Java 백준 문제풀이 (33) 2667: 단지 번호 붙이기

 

 

기초적인 그래프 알고리즘 문제를 풀 수 있다면 어려운 문제는 아니지만 배열 4방향, 8방향 탐색을 해보지 않았다면 어떻게 풀어야하는 지 난해하게 느껴질 수 있다.

우선 힌트를 줄테니 한 번 생각해보고 모르겠으면 정답을 보도록 하자.

 

 

 

평소 dfs, bfs 문제 풀 때와 달라진 것은 오직 한 가지 밖에 없다.

10분 고민해보고 모르겠으면 정답을 보자! 너무 오래 고민하는 것도 시간 낭비다.

전혀 어려운 문제가 아니기 때문에 이번 기회에 알아가면 다음부터는 분명히 풀 수 있을테니 걱정하지 않아도 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

정답

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int[][] map; // 지도
    static boolean[][] visited; // 탐색 여부 체크
    final static int[] FOUR_WAY_X = {1,-1,0,0}; // x축 탐색용 배열
    final static int[] FOUR_WAY_Y = {0,0,-1,1}; // y축 탐색용 배열
    static ArrayList<Integer> countArr = new ArrayList<>(); // 각 집 개수 배열
    static int counter = 0; // 탐색 시 집 개수 체크

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        userInput(br); // 인풋을 받아 값 대입
        findHouse(); // 집 탐색
        printAnswer(); // 정답 출력
    }

    private static void userInput(BufferedReader br) throws IOException {
        int T = Integer.parseInt(br.readLine());
        map = new int[T][T];
        visited = new boolean[T][T];
        int temp = 0;

        for (int i=0; i<T; i++) {
            String inputMap = br.readLine();
            for (int j=0; j<T; j++) {
                map[i][j] = Integer.parseInt(String.valueOf(inputMap.charAt(j)));
            }
        }
    }

    private static void findHouse() {
        for (int i=0; i<map.length; i++) {
            for (int j=0; j<map.length; j++) {
                if ( map[i][j] == 1 && !visited[i][j]) {
                    dfs(i,j);
                    countArr.add(counter);
                    counter=0;
                }
            }
        }
    }

    static void dfs(int x, int y) {
        visited[x][y] = true;
        counter++;

        for (int i=0; i< FOUR_WAY_X.length; i++) {
            x += FOUR_WAY_X[i];
            y += FOUR_WAY_Y[i];

            if ( x>=0 && y>=0 && x< visited.length && y< visited.length) {
                if (!visited[x][y] && map[x][y] == 1 ) {
                    dfs(x, y);
                }
            }

            x -= FOUR_WAY_X[i];
            y -= FOUR_WAY_Y[i];
        }
    }

    private static void printAnswer() {
        System.out.println(countArr.size());
        Collections.sort(countArr);
        for (int n : countArr) {
            System.out.println(n);
        }
    }




}

 

 

 

 

 

FOUR_WAY라는 배열을 두 개 만들어서 반복문을 돌려주면 좌표를 한 칸 씩 움직여서 체크하는 것을 하드코딩하지 않고 손쉽게 해결할 수 있다.

이 부분만 해결하면 나머지는 기초적인 dfs 문제 풀이와 똑같다.