[백준]BOJ 1012 유기농 배추(자바/BFS/메모리 초과)

 

 

배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 

 

위의 문제 조건을 처음 보았을때 BFS로 풀 수 있겠다고 생각했습니다.  서로 인접해있는 배추 그룹이 몇 그룹이 존재하는지를 알게되면 그건 곧 지렁이 개수를 구하는 것과 다름이 없다고 생각했습니다.

아래 그림과 같이 인접한 배추들을 그룹으로 묶어보면 총 5그룹이 나오는 것을 확인해볼 수 있었습니다.

 

예제 그림

 

 

 

 

저는 BFS로 탐색을 수행하며 인접한 배추들에 대해 방문처리를 진행했습니다. 그러나, 메모리 초과라는 문제가 발생했습니다. 

 

 

 

 

 

결론부터 말씀드리자면 메모리 초과의 원인은 바로 방문처리 문제였습니다!!!

항상 습관처럼 방문체크는 큐에서 pop한뒤 수행했었습니다. 다음과 같이요..

 

 

 

 

 

그러나, 해당 코드처럼 방문체크를 하게 되는 경우에는 방문 체크를 늦게 하기 때문에 중복된 값이 계속 큐에 삽입이되고 이러한 현상들이 누적되어 메모리 초과가 발생하는 것이었습니다. 따라서, 다음과 같이 큐에 넣기 전에 방문처리를 해주어애 합니다.

 

 

 

이렇게 큐에 넣기 전에 방문처리를 진행하여 문제를 해결할 수 있었습니다.

 

 

 

 

 

 

구현

public class Main_1012 {
	
	private static int[][] maps;
	private static int N;
	private static int M;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			
			maps = new int[N][M];
			
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				maps[y][x] = 1;
			}
			
			int result = 0;
			boolean[][] visited = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					//방문하지 않은 배추 좌표를 기준으로 BFS를 통해 인접한 배추를 탐색
					if(!visited[i][j] && maps[i][j] == 1) {
						solve(visited, i, j);
						result++;
					}
				}
			}
			System.out.println(result);
		}
		
	}
	
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	
	
	static void solve(boolean[][] visited, int x, int y) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {x, y});
		visited[x][y] = true;
		
		while(!queue.isEmpty()) {
			int[] tmp = queue.poll();
			int nowX = tmp[0];
			int nowY = tmp[1];
						
			for (int i = 0; i < dir.length; i++) {
				int nextX = nowX + dir[i][0];
				int nextY = nowY + dir[i][1];
				
				if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= M || visited[nextX][nextY] || maps[nextX][nextY] == 0) continue;
				
				visited[nextX][nextY] = true;
				queue.add(new int[] {nextX, nextY});
			}
		}
	}
	
	
	
}