DFS/BFS - 섬의개수

문제

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

분석/설계

맵을 탐색하는 DFS/BFS 유형의 문제이고 보통 2차원 배열 형태의 맵을 주고 조건을 달리하면서

탐색하는 형태 유형으로 많이 출제되는 것 같습니다.

기존 상하좌우만 탐색하는 케이스와 달리 대각선까지 탐색하기 때문에 이를 탐색하기 위한 값들을 잘 정의해줘야합니다.

구현 코드

package backjoon;

import java.util.Scanner;

public class Main {
	static int T; // 테스트 케이스 횟수
	static int M; // 배추 심어진 가로 길이
	static int N; // 배추 심어진 세로 개수
	static int K; // 배추가 심어진 위치의 개수
	static int[][] map; // 배추밭
	static boolean[][] visited; //
	static int cnt; // 필요한 지렁이 
	static int[] dx = {0, -1, 0, 1}; // 상하좌우 탐색을 위한 값들
	static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt(); // 테스트 케이스 개수
		
		for(int i=0; i<T; i++) {	// 입력 초기화
			cnt = 0;
			M = scanner.nextInt();
			N = scanner.nextInt();
			K = scanner.nextInt();
			
			map = new int[M][N];
			visited = new boolean[M][N];
			
			for(int j=0; j<K; j++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();	
				map[x][y] = 1;
			}
			
			for(int v=0; v<M; v++) {
				for(int w=0; w<N; w++) {
					if (map[v][w] == 1 && !visited[v][w]) {
						dfs(v, w);
						cnt++;
					}
				}
			}
			System.out.println(cnt);

		}
		scanner.close();
	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int mx = x + dx[i];
			int my = y + dy[i];
			
			if (mx >= 0 && my >= 0 && mx < M && my < N) { // 0 보다 크고 맵 크기보다는 작아야한다.
				if(!visited[mx][my] && map[mx][my] == 1) { // 방문 여부와 배추가 심어진 곳을 체크
					dfs(mx, my);
				}
			}
		}
	}
}

 

정리

입력받는 변수가 여러 개이므로 놓치지 않고 어떤 변수에 저장할지 정리하여

DFS 구현에 필요한 변수와 함께 정의합니다.

그 외에  탐색을 위한 값들도 정의해주고 이를 DFS 구현 시 적용하는 게 핵심입니다.

구현이 끝나면  간단하지만 어떻게 탐색하고 카운트할지 고민하고 구현에 들어가야 합니다.

참고

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