백준 알고리즘 - 4963_섬의 개수

문제 설명

1 : 땅, 0 : 바다
주어진 지도에서 섬이 몇 개인지 세는 문제이다.
1이 사방으로 이어져 있으면 한 개의 섬으로 간주된다.

문제 풀이

전에 풀었던 배추 문제와 거의 유사한 문제여서 빨리 풀었다.
배추 문제와 마찬가지로 dfs로 풀었다.
다른 점이 있다면 배추는 하나의 예제만 입력이 가능한데,
섬은 여러 개의 테스트케이스가 입력될 수 있다는 점이었다.

public static void main(String[] args) {
	int answer;
    
	while(true) {
		input();
        	if(x == 0 && y == 0) break;
          	...

0 0 이 들어올 때까지 input() 함수로 테스트케이스를 입력받도록 했다.

그랬더니 여러개의 테스트케이스를 처리하지 못하고 맨 처음 입력과 마지막 입력만 처리되었다.

문제는 Scanner 객체에 있었다.
나는 input() 내에서 Scanner 객체를 생성하고 있었기 때문에, while문을 돌때마다 Scanner 객체가 새로 생성되며 생긴 문제였다.
따라서 Scanner 를 전역함수로 선언해주니 해결되었다.

또한, 반복문을 돌며 재귀함수를 호출하기 전에 반드시 answer 을 초기화해줘야 이전 테스트케이스의 정답에서 count 되지 않는다.

전체 코드

public class Practice {
	static Scanner sc = new Scanner(System.in);
	static int x, y;
	static int[][] map;
	static boolean[][] visited;
	static List<Integer> numberOfLand = new ArrayList<>();
	
	public static void main(String[] args) {
		int answer;
		while(true) {
			input();
			
			if(x == 0 && y == 0) break;
			
			answer = 0;
			
			for(int i = 0; i < y; i++) {
				for(int j = 0; j < x; j++) {
					if(visited[i][j] == false && map[i][j] == 1) {
						visited[i][j] = true;
						dfs(i, j);
						answer++; 
					}
				}
			}
			numberOfLand.add(answer);
		}
		
		for(int n = 0; n < numberOfLand.size(); n++) {
			System.out.println(numberOfLand.get(n));
		}
	}


	private static void dfs(int i, int j) {
		int[] dy = {-1, 1, 0, 0, -1, 1, 1, -1};
		int[] dx = {0, 0, 1, -1, 1, -1, 1, -1};
		
		int ny = 0;
		int nx = 0;

		for(int d = 0; d < 8; d++) {
			ny = dy[d] + i;
			nx = dx[d] + j;
			
			if(isArrange(ny,nx) && visited[ny][nx] == false && map[ny][nx] == 1) {
				visited[ny][nx] = true;
				dfs(ny,nx);
			}
		}
	}


	private static boolean isArrange(int ny, int nx) {
		return ny >= 0 && nx >= 0 && ny < y && nx < x;
	}


	private static void input() {
		
		x = sc.nextInt();
		y = sc.nextInt();
		
		//System.out.println("x: "+x+" y: "+y);
		
		map = new int[y][x];
		visited = new boolean[y][x];
		for(int i = 0; i < y; i++) {
			for(int j = 0; j < x; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		/*
		for(int i = 0; i < y; i++) {
			for(int j = 0; j < x; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}*/
		
	}
}

Git gist 주소

https://gist.github.com/ysyS2ysy/18e0f253b91bf5fd0e6f604dd0558e91