BOJ 2667) 단지번호붙이기

문제를 보고 상하좌우 4방향을 검사하여 방문한 적이 없는 집이 하나도 없으면 새로 방문하는 단지로 풀면 되겠다 생각헸는데, 탐색 순서를 보면 문제 예제의 2번같은 경우 다른 쪽 끝을 먼저 탐색할 경우 단지의 개수를 증가시키는 연산을 하게되어 단지수를 정확하게 계산할 수 없게 되어 문제가 생긴다. 당연하게도 단지 내 집의 개수도 계산할 수 없다.

 

무엇보다도 이런 좌표탐색 문제의 경우 한 부분을 완료하고 다음 부분으로 넘어가야지 위와 같은 문제가 발생하지 않는다.

 

dfs가 떠오르지 않은 것은 아니지만 dfs는 사용하기 망설여지는게 input이 과하게 클경우 시간초과가 너무 많이나서 꺼려지게됨.

 

> DFS의 시간복잡도는 리스트의경우 O(|V|+|E|), 인접행렬의 경우 O(V^2)이므로

행렬의 최대크기가 25*25=625인 이문제의 경우 V^2의 시간복잡도를 가져도 괜찮다.

 

//접근을 잘못한 코드

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

public class Main {

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

        //0: 집없음 1:방문X집
        int[][] arr = new int[N][N];
        boolean[][] visited = new boolean[N][N];
        //주변 4개의 집이 모두 방문한적 없을경우 단지수++
        boolean flag;
        boolean edited = true;
        int rst = 0;

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<N; j++) {
                arr[i][j] = str.charAt(j)-'0';
            }
        }

        while(edited) {
            edited=false;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (arr[i][j] == 1 && !visited[i][j]) {
                        visited[i][j] = true;
                        flag = true;
                        //4방향중에 한곳이라도 방문한적 있을경우 flag=false;
                        if (i > 0 && visited[i-1][j]) {
                            flag = false;
                        }
                        if (j > 0 && visited[i][j-1]) {
                            flag = false;
                        }
                        if (i < N-1 && visited[i+1][j]) {
                            flag = false;
                        }
                        if (j < N-1 && visited[i][j+1]) {
                            flag = false;
                        }
                        //4방향에 방문하지 않은 집이 존재할 경우
                        if (i > 0 && arr[i-1][j] == 1) {
                            edited = true;
                        }
                        if (j > 0 && arr[i][j-1] == 1) {
                            edited = true;
                        }
                        if (i < N-1 && arr[i+1][j] == 1) {
                            edited = true;
                        }
                        if (j < N-1 && arr[i][j+1] == 1) {
                            edited = true;
                        }

                        if (flag) rst++;
                    }
                }
            }
        }

        System.out.println(rst);
    }
}

 

 

 

//최종 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class Main {

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

        //0: 집없음 1: 방문X집
        int[][] arr = new int[N][N];
        boolean[][] visited = new boolean[N][N];
        Stack<Location> stack = new Stack();
        List<Integer> list = new ArrayList<>();
        int rst = 0;

        //input 받기
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<N; j++) {
                arr[i][j] = str.charAt(j)-'0';
            }
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(arr[i][j]==1 && !visited[i][j]) {
                    Location loc = new Location(i,j);
                    stack.push(loc);
                    int houseNum = 0;
                    visited[i][j] = true;
                    houseNum++;

                    while(!stack.isEmpty()) {
                        Location peekLoc = stack.peek();
                        int x = peekLoc.x;
                        int y = peekLoc.y;

                        boolean flag = true;

                        if(x>0 && arr[x-1][y]==1 && !visited[x-1][y]) {
                            visited[x-1][y] = true;
                            houseNum++;
                            Location l = new Location(x-1, y);
                            stack.push(l);
                            flag = false;
                        }
                        if(y>0 && arr[x][y-1]==1 && !visited[x][y-1]) {
                            visited[x][y-1] = true;
                            houseNum++;
                            Location l = new Location(x, y-1);
                            stack.push(l);
                            flag = false;
                        }
                        if(x<N-1 && arr[x+1][y]==1 && !visited[x+1][y]) {
                            visited[x+1][y] = true;
                            houseNum++;
                            Location l = new Location(x+1, y);
                            stack.push(l);
                            flag = false;
                        }
                        if(y<N-1 && arr[x][y+1]==1 && !visited[x][y+1]) {
                            visited[x][y+1] = true;
                            houseNum++;
                            Location l = new Location(x, y+1);
                            stack.push(l);
                            flag = false;
                        }

                        if(flag) stack.pop();
                    }

                    rst++;
                    list.add(houseNum);
                }
            }
        }

        System.out.println(rst);
        Collections.sort(list);
        for (Integer integer : list) {
            System.out.println(integer);
        }


    }

    static class Location {
        int x;
        int y;

        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

스택을 이용한 dfs로 구현하였다. 집들을 탐색하다가 1이 보이면 그 집에서 연결되는 모든 노드들을 묶어서 한개의 단지를 만드는 방식으로 구현함.

 

조심할 점은 스택으로 dfs를 구현할때 초기값 설정은 반드시 while문 전에 시행되어야 함. while문내에서 초기화를 할경우 그부분이 반복되면서 의도치 않게 동작할 수 있다.

 

또 dfs에서 확장이 이루어지는 노드인지, leaf인지 여부를 확인해야 할 경우 flag변수를 별도로 선언해서 확인했는데, 이거말고 다른 방법은 없을까