백준 Q2667 - 단지 번호 붙이기

---

한 노드를 기준으로 상하좌우를 탐색하는 유형의 문제이다. 객체를 생성하여 풀 수도 있지만 익숙한 2차원 배열을 사용하였다.

DFS를 사용할것이기 때문에 static 변수들을 몽땅 선언하자.

static int N, eachHome;
static int[][] map;
static boolean[][] visited;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static List<Integer> houseCount;

변수 설명

• eachHome: 각 단지별 아파트의 개수
• map: 지도의 크기만큼 2차원 배열을 생성
• houseCount: 각 단지별 eachHome을 저장하는 메서드
• dx,dy: 상,하,좌,우 탐색을 위한 방향벡터

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		if (map[i][j] == 1 && !visited[i][j]) {
			eachHome = 1;
			dfs(i, j);
            houseCount.add(eachHome);
        }
    }
}

2차원 배열의 모든 원소를 방문하며 조건에따라 DFS를 진행하는 로직이다.
2중 for문을 사용하지 않고 어떻게 각각의 원소를 방문하는지 생각해봤는데, 그냥 단순하게 for문을 사용하고, DFS 진행시 방문여부를 true 해주면 된다.

이때 체크한 방문여부를 근거로 for문에서 각각의 원소 방문시 값이 1인 배열의 원소 + 방문하지 않은 원소 만 DFS를 진행할 지 체크해주면 되는것이다.

private static void dfs(int i, int j) {
	visited[i][j] = true;
	for (int k = 0; k < 4; k++) {
		int nextX = i + dx[k];
		int nextY = j + dy[k];

		if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N 
        		&& !visited[nextX][nextY] && map[nextX][nextY]==1) {
			eachHome++;
			dfs(nextX, nextY);
		}
	}
}

각 단지에 대해 DFS를 시작하면 곧바로 방문여부를 true로 바꾸고, dfs를 진행하기 위해 방향벡터를 사용하여 현 시점 기준 상,우,하,좌 네 가지 방향을 모두 체크한다.

nextX >= 0 && nextY >= 0 && nextX < N && nextY < N

• 인덱스가 0보다 크고 2차원 배열 크기보다 작아야하는 조건이다

!visited[nextX][nextY] && map[nextX][nextY]==1

• 원소 값이 1임과 동시에 방문하지 않은 원소여야한다.
• 여기서 방문여부를 체크하지 않으면 DFS는 종료되지 않고 무한반복 될 것이다

---

최종 코드

public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int N, eachHome;
    static List<Integer> houseCount;

    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 + 1][N + 1];
        visited = new boolean[N + 1][N + 1];
        houseCount = new ArrayList<>();
        eachHome = 1;

        // 지도 초기화
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    eachHome = 1;
                    dfs(i, j);
                    houseCount.add(eachHome);
                }
            }
        }

        Collections.sort(houseCount);

        System.out.println(houseCount.size());
        for (Integer i : houseCount) {
            System.out.println(i);
        }
    }

    private static void dfs(int i, int j) {
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int nextX = i + dx[k];
            int nextY = j + dy[k];

            if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N 
            		&& !visited[nextX][nextY] && map[nextX][nextY]==1) {
                eachHome++;
                dfs(nextX, nextY);
            }
        }
    }
}

---

풀이 후기

1인 원소의 값을 0으로 바꾸는 방법으로 방문여부를 체크

이게 가장 처음에 생각했던 아이디어인데 나름 창의적인 방식이라고 생각한다.
처음에 모든원소에 접근하기 위해 2중 for문을 사용할 생각을 못했기 때문에 해당 아이디어로 구현하지 못했어서 이후에 리팩토링을 해보았다.

private static void dfs(int i, int j) {
	// 방문했음을 표시하기 위해 1에서 0으로 바꿈
	map[i][j] = 0;
	for (int k = 0; k < 4; k++) {
		int nextX = i + dx[k];
		int nextY = j + dy[k];

		if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N 
        		&& map[nextX][nextY] == 1) {
			eachHome++;
			dfs(nextX, nextY);
		}
	}
}

dfs 코드를 위와같이 구성하면 방문여부를 확인 할 필요도 없고, dfs 시작 조건에서도 아래와 같이 방문여부 체크를 빼고 1인 경우만 확인하면 된다.

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		if (map[i][j] == 1) {
			eachHome = 1;
			dfs(i, j);
			houseCount.add(eachHome);
		}
	}
}

위에가 1로 바꾸는 방식, 아래가 visited 배열 사용한 방식

음 코드의 길이는 당연히 줄었을 것이고, static 변수도 줄었으니 메모리 공간도 아낄 수 있지만 크게 차이가 나는 것 같지는 않다.
그래도 줄었으면 좋은거 아니겠는가