[백준2667] 단지번호붙이기 - 완전탐색, 그래프탐색, dfs, bfs

문제

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

문제 분석

시간 복잡도

• N x N 지도 (N = 25)
• 영역 탐색 (그래프 탐색)
• 중복방문 X
• O( N ^ 2)

문제 유형

• 그래프 탐색
• 시간 복잡도 상, 완전탐색 (dfs, bfs) 가능

 

설계

dfs와 bfs는 기본적으로 "탐색" 알고리즘이다. 따라서,

1. 연결된 곳 (순회할 수 있는 곳)이 어디있는지 파악
2. 연결된 곳으로 방문할 수 있는지 파악

하는 것이 중요하다. 해당 문제의 경우,

연결된 곳은 "현재 방문한 지점"의 상.하.좌.우 인접한 칸이 될 것이다.

갈 수 있는 곳은 1. 배열 안이며, 2. 방문 안한 지점이며, 3. 집인 지점이 된다.

 

 

방문을 했다면 기본적으로 "체크인(방문체크)"를 해주어야 한다. dfs와 bfs의 동작 구조의 차이에 대해 주목하자.

• dfs
  방문: 재귀 메소드 콜
• bfs
  방문: 큐에서 꺼내오는 행위
  체크인: 큐에 넣을 때

 

bfs의 체크인을 큐에서 꺼내올 때 하지 않고, 큐에 넣을 때 해야함을 주목하자. bfs는 큐를 활용한 탐색기법이고, 큐에 들어있는 엘레멘트는 "방문예정"인 곳을 의미한다. 그렇다면, 큐에 넣는 행위는 "방문예정"으로 등록하는 행위인데, 큐에서 꺼내올 때가 아닌 큐에 넣을 때 체크인을 해야할까? 큐에 넣을 때 체크인을 해야만, "방문예정"인 곳을 중복해서 큐에 넣지 않기 때문이다.

 

 

dfs 설계

1. 체크인: 방문체크
2. 목적지: 없음
3. 연결된 곳: 현재 방문한 지점의 상.하.좌.우 인접한 칸
4. 갈 수 있는가?: 1) 배열 내부, 2) 방문 안한 지점, 3) 집('1')인 지점
5. 체크아웃: 없음

수도코드

dfs(int x, int y) {
// 체크인
visited[x][y] = true;
...
    //연결된 곳
    for(d: 상.하.좌.우) {
    	int nx = x + d;
        int ny = y + d;
        // 갈 수 있는가?
        if(배열 안, 방문 안함, 집임) {
        	dfs(nx, ny);
        }
    }
...
}

 

bfs 설계

1. 목적지: 없음
2. 연결된 곳: 현재 방문한 지점의 상.하.좌.우 인접한 칸
3. 갈 수 있는가?: 1) 배열 내부, 2) 방문 안한 지점, 3) 집('1')인 지점
4. 체크인: 방문체크
5. 큐에 넣음

 

수도코드

bfs() {
//..
starting point setting
..//

while(큐 빌때까지) {
	// 큐에서 꺼냄(방문)
    int x = ~~
    int y = ~~
    
    // 목적지인가?(없음)
    
    // 연결된 곳
    for (d: 상.하.좌.우) {
    	int nx = x + d;
        int ny = y + d;
        // 갈 수 있는가?
        if(board[nx][ny] = 배열 안, 방문 안함, 집임) {
        	// 체크인
            visited[nx][ny] = true;
            // 방문 예정 등록
            queue.add(nx ,ny);
        }
    }
}
}

 

구현

코드

public class BOJ2667단지번호붙이기 {
	static final char HOUSE = '1';
	static int N, houseCount, complexCount;
	static List<Integer> houseCountAnswers = new ArrayList<>();
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static char[][] board;
	static boolean[][] visited;

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

		N = Integer.parseInt(br.readLine());
		board = new char[N][N];
		visited = new boolean[N][N];
		for (int row = 0; row < N; row++) {
			board[row] = br.readLine().toCharArray();
		}

		for (int row = 0; row < N; row++) {
			for (int col = 0; col < N; col++) {
				if (!visited[row][col] && board[row][col] == HOUSE) {
					houseCount = 0;
					complexCount++;
//					dfs(row, col);
					bfs(row, col);
					houseCountAnswers.add(houseCount);
				}
			}
		}

		Collections.sort(houseCountAnswers);

		System.out.println(complexCount);
		for (int houseCount : houseCountAnswers) {
			System.out.println(houseCount);
		}
	}

	private static void dfs(int x, int y) {

		houseCount++;
		visited[x][y] = true;
		// base case (x)

		// recursive case
		for (int direct = 0; direct < 4; direct++) {
			int nx = x + dx[direct];
			int ny = y + dy[direct];

			if (isInRange(nx, ny) && !visited[nx][ny] && board[nx][ny] == HOUSE) {
				dfs(nx, ny);
			}
		}
	}

	private static void bfs(int startX, int startY) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { startX, startY });
		visited[startX][startY] = true;

		while (!queue.isEmpty()) {
			houseCount++;
			// 큐에서 뺀다
			int[] pos = queue.poll();
			int x = pos[0];
			int y = pos[1];
			// 목적지인가? (x)

			// 연결된 곳 순회
			for (int direct = 0; direct < 4; direct++) {
				int nx = x + dx[direct];
				int ny = y + dy[direct];
				// 갈 수 있는가?
				if (isInRange(nx, ny) && !visited[nx][ny] && board[nx][ny] == HOUSE) {
					// 체크인
					visited[nx][ny] = true;
					// 큐에 넣음
					queue.add(new int[] { nx, ny });
				}
			}
		}
	}

	private static boolean isInRange(int x, int y) {
		return 0 <= x && x < N && 0 <= y && y < N;
	}
}

 

결과

 

기록

• 날짜: 2022-12-22
• 소요시간: 20분