[백준] 4963 섬의 개수 - DFS(깊이우선탐색) JAVA

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

코드설명

DFS(깊이우선탐색) 을 활용합니다.

 

DFS로 이미 방문했던 섬은 다시 방문하지 않도록 visited를 처리하면 됩니다.

풀면서 실수했었던 점은, 전역변수로 이미 W와 H가 선언되어있었는데, main 함수 내에서

int W, int H 에 값을 선언했기에, 지역변수에 해당 값이 들어가서 DFS함수에서의 H와 W(즉, 전역변수)에는 0 이 들어가있었습니다. 이 때문에, 어떤 오류인지 디버깅하느라 시간이 소요되었습니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, C, H, W, K, M, T;
	public static int answer = 0;
	public static int[][] map;
	public static int[][] visited;
	public static int[] dx = {-1,-1,-1, 0, 1, 1, 1, 0};
	public static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			if(H == 0 && W == 0) break;
			map = new int[H][W];
			visited = new int[H][W];
			answer = 0;
			for(int i=0;i<H; i++) {
				Arrays.fill(visited[i], - 1);
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			for(int i=0;i<H; i++) {
				for(int j=0; j<W; j++) {
					if(visited[i][j] == -1 && map[i][j] == 1) {
						visited[i][j] = 1;
						answer += DFS(0, i, j);
					}
				}
			}
			
			System.out.println(answer);
		}
		
	}
	public static int DFS(int depth, int r, int c) {
		for(int dir = 0; dir < 8; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(nr < 0 || nr >= H || nc < 0 || nc >= W) {
				continue;
			}
			if(visited[nr][nc] != -1) continue;
			if(map[nr][nc] == 0) continue;
			visited[nr][nc] = 1;
			DFS(depth + 1, nr, nc);
		}
		return 1;
	}
	
}