[백준 4963]bfs : 섬의 개수(java)-메모리 초과 문제

문제보러가기

4963번: 섬의 개수

 

이문제는 전형적인 탐색 문제로 연결된 영역이 몇 개가 있는지 구하는 문제였다. 다른 점이라면 위, 아래, 오른쪽, 왼쪽이 아닌 대각선 포함 8방향으로 탐색해야 한다는 점.

 

 

 

 

 

 

문제풀이

-map [][]에 입력받은 값을 저장해준다.

-map을 이중 for문으로 탐색하면서 1일 경우(섬일 경우) 그리고 방문하지 않았을 경우에 bfs()를 수행한다.

-4방향이 아닌 대각선 포함 8방향으로 체크해주면서 연결된 섬의 개수를 체크한다.

 

 

사실 이문제는 "메모리 초과" 때문에 게시글을 쓰게 되었다.

아래 코드 부분에서 방문 배열을 체크해주는 visited [sx][sy] = true; 이 부분의 위치를 잘 보자!

 

package baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Ex_4963 {

	static int w = -1;
	static int h = -1;
	static int[][] map;
	static boolean[][] visited;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//bfs 섬의 개수
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		w = -1;
		h = -1;
 		while(true) {
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			int cnt=0;
			if(w==0 && h==0) break;
			map = new int[h][w];
			visited = new boolean[h][w];
			for(int i=0;i<h;i++) {
				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(map[i][j]==1 && !visited[i][j]) {
						bfs(new Pair(i,j));
						cnt++;
					}
				}
			}
			
			sb.append(cnt+"\n");
			
			
		}
 		System.out.println(sb);
 
	}
	static void bfs(Pair start) {
		int[] dx = {0,1,0,-1,1,-1,1,-1};
		int[] dy = {1,0,-1,0,1,-1,-1,1};
		Queue<Pair> q = new LinkedList<>();
		q.add(start);
		while(!q.isEmpty()) {
			Pair p = q.poll();
//			visited[p.x][p.y] = true; //여기에서 하면 메모리 초과 발생
			for(int i=0;i<8;i++) {
				int sx = p.x+dx[i];
				int sy = p.y+dy[i];
				
				if(sx < 0 || sy < 0|| sx >= h || sy >= w)
					continue;
				if(map[sx][sy]==0 || visited[sx][sy]) 
					continue;
				q.add(new Pair(sx,sy));
				visited[p.x][p.y] = true;
				visited[sx][sy] = true; //여기서 체크해줘야 중복방지로 메모리 초과하지 않음
			}
		}
		
	}

}
class Pair{
	int x;
	int y;
	Pair(int x,int y){
		this.x = x;
		this.y = y;
	}
	
}

 

가벼운 마음으로 풀다가 메모리 초과가 떠서 당황했던 문제이다 ㅎ,,,