섬나라 아일랜드 (DFS /BFS)

고찰.

1. DFS 인자 아무생각없이 1,1 넣는 실수
2. map[i][j]=0를 초기화하지 않음. (DFS/BFS 방향 탐색 시, 다시 0으로 세팅 되긴 하지만 초기화 잊지 않는 것이 좋음)
3. M.DFS(i, j, map); => 발견하기 까지 오래걸렸음.

 

package com.test.testapplication;

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

class Main {

	static int m, n, answer;

	int[] dx = { 0, 0, 1, -1, 1, 1, -1, -1 };
	int[] dy = { 1, -1, 0, 0, 1, -1, -1, 1 };

	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);

		n = in.nextInt();

		int[][] map = new int[n + 1][n + 1];

		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				map[i][j] = in.nextInt();
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if( map[i][j] == 1) {
					//System.out.println(String.format("%d %d",i,j));
					//DFS 인자 1,1 넣는 실수...
					//map[i][j]=0를 초기화하지 않음.
					//M.DFS(i, j, map);
					map[i][j]=0;
					M.BFS(i, j, map);
					answer ++;					
				}
			}
		}
		System.out.println(answer);
	}

	private void DFS(int px, int py, int[][] map) {

		for (int i = 0; i < 8; i++) {
			int nx = px + dx[i];
			int ny = py + dy[i];
			if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && map[nx][ny] == 1) {		
				map[nx][ny] = 0;
				DFS(nx, ny, map);
			}
		}
	}
	
	private void BFS(int x, int y, int[][]map) {
		Queue<Position> Q = new LinkedList<>();
		
		Q.offer(new Position(x, y));
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			for ( int i = 0 ; i < len ; i++) {
				Position p = Q.poll();
				
				for ( int j = 0 ; j < 8 ; ++j) {
					int nx = p.x + dx[j];
					int ny = p.y + dy[j];
					if ( nx>=1 && nx <= n && ny >= 1 && ny <= n && map[nx][ny] == 1) {
						map[nx][ny] = 0;
						Q.offer(new Position(nx, ny));
					}	
				}
			}
		}
	}
	class Position{
		int x,y;
		Position(int x, int y){
			this.x=x;
			this.y=y;
		}
		
	}

}

ex)
input
7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0
output
5