DFS/BFS - 단지번호붙이기

문제

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

분석/설계

DFS와 BFS로 완전 탐색하여 접근하는 방향으로 가닥을 잡고

인접한 상하좌우를 탐색하는 것이므로 BFS가 구현이 쉬울 것 같아 선택했다.

다른 문제들과 달리 한칸씩 띄워서 입력 받지 않기때문에 이런 부분이 조금 달랐던 것 같고

결국 입력 값을 받아 초기화하고 BFS로 어떻게 기준을 잡고 탐색하는지가 중요했던 문제입니다.

구현 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Dot{ // X,Y 좌표를 저장하는 클래스
	int x;
	int y;
	
	public Dot(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}				
}

public class Main {
	static ArrayList<Integer> count = new ArrayList<>();
	 // 상, 하, 좌, 우를 탐색하기 위한 배열
	static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
	
	public static void bfs(int arr[][], boolean visited[][], Dot dot) {
		Queue<Dot> q = new LinkedList<Dot>();
		q.offer(dot);
		visited[dot.getX()][dot.getY()] = true;
		int cnt = 0; // 주변에 존재하는 집의 수를 저장
		
		while(!q.isEmpty()) {
			Dot temp = q.poll();
			int x = temp.getX();
			int y = temp.getY();
			cnt++;
			
			for(int i=0; i<4; i++) { // 상하좌우 탐색
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				// 맵의 범위를 벗어나는 좌표는 무시
				if(nx>=arr.length || nx<0 || ny>=arr[nx].length || ny < 0) continue;
				
				// 이미 방문한 경우도 무시
				if(visited[nx][ny]) continue;
				
				if(arr[nx][ny] == 1) {
					visited[nx][ny] = true;
					q.offer(new Dot(nx, ny));
				}
			}
		}
		count.add(cnt);
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt(); // 맵의 크기 N
		int arr[][] = new int[N][N]; // N x N map
		boolean visited[][] = new boolean[N][N]; // N x N 크기의 방문여부 배열
		
		scanner.nextLine();
		for(int i=0; i<arr.length; i++) { // 맵 입력 받은 값으로 초기화
			String[] temp = scanner.nextLine().split("");
			for(int j=0; j<arr[i].length; j++) {
				arr[i][j] = Integer.parseInt(temp[j]);
			}
		}
		Dot dot;
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr[i].length; j++) {
				if(arr[i][j] == 1 && visited[i][j] == false) { // 맵을 탐색하면서 아파트이면서 방문하지 않은경우
					dot = new Dot(i, j);
					bfs(arr, visited, dot);
				}
			}
		}
			
		System.out.println(count.size());
		Collections.sort(count);
		for(int i=0; i<count.size(); i++) {
			System.out.println(count.get(i));
		}
		
		
		scanner.close();
	}
}

 

정리

좌표에 대해서 어떻게 코드로 구현할지

BFS를 구현할 때 큐에 넣고 큐에서 꺼내는 기준을 무엇으로 할지가 핵심이고

답을 구하기 위해서 어떤 값이 필요할지 처음에 잘 정의한다면 그렇게 어려운 문제는 아닙니다.

FS나 DFS를 어떻게 응용할지 많이 문제를 접해봐야할 것 같습니다.

참고

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