단지번호붙이기(2667번)

• 티어 : Sliver 1
• 정답여부 : 오답
• 알고리즘 유형 : 그래프이론, 그래프탐색, 너비 우선 탐색,깊이 우선 탐색
• 시간 제한 : 1초

💡문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

💡입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

💡출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

💡예제 입력 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

💡예제 출력 1

3
7
8
9

💡문제요약

단지 아파트 내에 1 즉 단지 번호끼리 붙어있는 아파트 갯수를 구하면 되는 문제

💡알고리즘 설계

• N: 지도 크기
• count: 각 아파트 단지의 크기를 세는 카운터, 1로 초기화
• map: 아파트 단지 지도를 나타내는 2차원 배열
• visit: 지도의 방문 여부를 추적하는 2차원 배열
• result: 발견된 모든 아파트 단지의 크기를 저장하는 ArrayList

1. x와 y 기준으로 DFS를 이용하여 한칸씩 단지 내에 아파트가 있는지 한칸씩 이동하면서 확인해본다. 만약 있으면 count ++
2. 단지내에 총 아파트를 구하면 result에 값을 넣어준다.
3. map에 총 단지 갯수와 단지 내에 있는 아파트 수를 출력한다.

💡작성코드

• Java

import java.util.*;
import java.io.*;
public class Main{	
	static int N;
	static int count = 1;
	static int[][] map;
	static boolean[][] visit;
	static ArrayList<Integer> result = new ArrayList<>();
	// 기준행을 기준으로 방문하지 않은 곳이면서 1의 값을 가지는 곳을 상,하,좌,우로 살펴보는 과정	
	static void dfs(int x, int y) {
		visit[x][y] = true; // 단지내 있느 아파트 기준으로 시작 count는 1로 초기회 하여 굳이 ++할 이유가 없음.
		if (y < map.length-1 && map[x][y+1]== 1 && !visit[x][y+1]) {
			count ++;
			dfs(x, y+1);
		}
		if(x <map.length-1 && map[x+1][y]== 1 && !visit[x+1][y]) {
			count++;
			dfs(x+1,y);
		}
		if(y >0 && map[x][y-1] == 1 && !visit[x][y-1]) {
			count ++;
			dfs(x,y-1);
		}
		if(x > 0 &&map[x-1][y] == 1 && !visit[x-1][y]) {
			count ++;
			dfs(x-1,y);
		}
	}	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); // 주어진 map크기를 입력받음
		map = new int [N][N]; // 아파트 단지 크기
		visit = new boolean[N][N]; // 방문
		for(int i =0; i < N; i++) {
			String row = br.readLine();
			for(int j = 0; j < N; j++) {
				map[i][j] =row.charAt(j)-'0';
			}
		}
		for(int i =0; i< map.length; i++) {
			for(int j = 0; j<map[i].length; j++) {
				if(map[i][j] == 1 && !visit[i][j]) {
					count = 1;
					dfs(i,j);
					result.add(count);
				}
			}
		}
		System.out.println(result.size());
		Collections.sort(result);
		for(int i =0; i < result.size(); i++) {
			System.out.println(result.get(i));
		}
	}	
}

💡시간복잡도

O(N^2)

💡틀린 이유 or 수정할 부분

처음에 count의 값을 1로 설정해주지 않아서 틀렸다. ㅎㅎ 원래 시작점이 아파트가 있다라고 가정해서 count를 1로 설정해줘야 했는데 자꾸 실수가 많다 ..ㅠㅠ

나는 DFS로 구현했지만 이 문제는 뭔가 BFS로 풀기에 적당한 거 같다! 그래서 BFS로 푸신분들의 코드를 가져왔다.

💡틀린 부분 수정 or 다른풀이

• Java

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.*;
public class Q_2667_AttachNumber_20210521 {
    public static int n;
    public static int[][] map;
    public static boolean[][] visited;
    // 상좌하우
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static int count;
    public static List<Integer> result = new ArrayList();
    public static void solution() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    count = 0;
                    dfs(i, j);
                    result.add(count);
                }
            }
        }
    }
    public static void dfs(int curR, int curC){
        // 방문 처리
        visited[curR][curC] = true;
        count ++;
        for (int dir = 0; dir < 4; dir++) {
            int nextR = curR + dx[dir];
            int nextC = curC + dy[dir];
            // 범위를 벗어나면 반복문 넘어가기
            if(nextR < 0 || nextC < 0 || nextR >= n || nextC >=n) continue;
            else if(map[nextR][nextC] == 1 && !visited[nextR][nextC]){
                dfs(nextR, nextC);
            }
        }
    }
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visited = new boolean[n][n];
        for(int i=0 ; i<n ; i++) {
            String temp = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = temp.charAt(j) - '0';
            }
        }
        solution();
        Collections.sort(result); // list 오름차순 정렬
        bw.write(result.size()+"\n");
        for (int i = 0; i < result.size(); i++) {
            bw.write(result.get(i)+"\n");
        }
        br.close();
        bw.close();
    }
}

💡느낀점 or 기억할 정보

나는 하나하나 상하좌우를 조건식을 줘서 풀었지만 다른 블로그를 보니 좀더 간단하게 구현하신분이 계셨다. 나도 저렇게 좌라락 간단하게 하고 싶었지만 아직 그럴 짬밥이 없기에 그냥 하나하나 기준으로 노동적이게 코드를 구현한거 같다. 좀 더 다른사람의 코드를 보고 내 코드로 만들어야겠다는 생각이 든다.