[백준] 3184 양 - BFS(넓이우선탐색) JAVA

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

코드설명

 BFS(넓이우선탐색) 를 활용하면됩니다.

 

문제에서 주어지듯, 마당에서 "탈출"할 수 있는 칸일 경우 어떤 영역에도 속하지 않는다고 가정합니다.

그러므로, 저는 바깥에 마당으로 나올 수 있게 빈필드를 새로 추가했습니다.

matrix = new char[N + 2][M + 2];

이와 같이 처리할경우 행에 + 2만큼, 열에 + 2 만큼 사이즈는 늘어납니다. 하지만 훨씬 더 쉽게 바깥과 연결된 필드를 체크할 수 있으므로 이와 같이 구현했습니다.

 

이외 각 구역의 Counting하는 것은 일반적인 BFS구현입니다.

코드

정답코드1입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int[] answer = new int[2];
	static char[][] matrix;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		matrix = new char[250 + 2][250 + 2];

		for(int i=0; i<N+2; i++) {
			Arrays.fill(matrix[i], '.');
		}
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for(int j=1; j<=M; j++) {
				matrix[i][j] = str.charAt(j - 1);
			}
		}

		//먼저 밖에 연결된 칸을 모두 울타리로 바꾸어준다.
		coloringBFS(0, 0);

		for(int i=2; i<N; i++) {
			for(int j=2; j<M; j++) {
				if(matrix[i][j] != '#') {
					int[] temp = countSheepWolf(i, j);
					answer[0] += temp[0]; answer[1] += temp[1];
				}
			}
		}
		for(int v : answer) System.out.print(v+" ");
	}
	
	static void coloringBFS(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc});
		matrix[sr][sc] = '#';
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			for(int[] dir : new int[][] { {0, 1}, {0, -1}, {1, 0}, {-1, 0}}){
				int nr = temp[0] + dir[0];
				int nc = temp[1] + dir[1];
				
				if(nr < 0 || nr >= N + 2 || nc < 0 || nc >= M + 2) continue;
				if(matrix[nr][nc] == '#') continue;
				matrix[nr][nc] = '#';
				q.offer(new int[] {nr, nc});
			}
		}
	}
	
	static int[] countSheepWolf(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc});
		int wolfCnt = 0;
		int sheepCnt = 0;
		if(matrix[sr][sc] == 'v') wolfCnt+=1;
		else if(matrix[sr][sc] == 'o') sheepCnt += 1;
		matrix[sr][sc] = '#';
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			int r = temp[0], c = temp[1];

			for(int[] dir : new int[][] {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}) {
				int nr = r + dir[0];
				int nc = c + dir[1];
				
				if(nr < 1 || nr >= N+1 || nc < 1 || nc >= M + 1) continue;
				if(matrix[nr][nc] == '#') continue;
				
				if(matrix[nr][nc] == 'v') wolfCnt+=1;
				else if(matrix[nr][nc] == 'o') sheepCnt += 1;
				matrix[nr][nc] = '#';
				q.offer(new int[] {nr, nc});
			}
		}
		
		int[] ret = new int[2];
		if(wolfCnt < sheepCnt) {
			ret[0] = sheepCnt;
		}else if(wolfCnt >= sheepCnt) {
			ret[1] = wolfCnt;
		}
		return ret;
	}
	
	
	
	
}

 

오답코드1입니다.

정답코드1과 거의 유사하지만, 방문처리를 빠르게하지않아 큐가 불필요하게 쌓여 메모리초과가 발생하는 코드입니다.

아래의 코드에서 유의깊게 볼 부분은 countsheepWolf(int sr, int sc) 함수입니다.

while(!q.isEmpty()) {
    int[] temp = q.poll();
    int r = temp[0], c = temp[1];
    if(matrix[r][c] == 'v') wolfCnt+=1;
    else if(matrix[r][c] == 'o') sheepCnt += 1;
    matrix[r][c] = '#';

이 코드를 보면 방문처리를 큐에 넣은것을 빼면서 하고 있습니다.

그렇게 할경우, 물론 방문처리는 되겠지만, 큐에 넣으면서 바로 처리가 안되면서 방문처리 타이밍에 따라 이미 방문했음에도 처리되지 않는 경우가 있습니다. 그러므로, 큐에 넣을떄 바로 방문처리를 하도록 합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int[] answer = new int[2];
	static char[][] matrix;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		matrix = new char[250 + 2][250 + 2];

		for(int i=0; i<N+2; i++) {
			Arrays.fill(matrix[i], '.');
		}
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for(int j=1; j<=M; j++) {
				matrix[i][j] = str.charAt(j - 1);
			}
		}

		//먼저 밖에 연결된 칸을 모두 울타리로 바꾸어준다.
		coloringBFS(0, 0);

		for(int i=2; i<N; i++) {
			for(int j=2; j<M; j++) {
				if(matrix[i][j] != '#') {
					int[] temp = countSheepWolf(i, j);
					answer[0] += temp[0]; answer[1] += temp[1];
				}
			}
		}
		for(int v : answer) System.out.print(v+" ");
	}
	
	static void coloringBFS(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc});
		matrix[sr][sc] = '#';
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			for(int[] dir : new int[][] { {0, 1}, {0, -1}, {1, 0}, {-1, 0}}){
				int nr = temp[0] + dir[0];
				int nc = temp[1] + dir[1];
				
				if(nr < 0 || nr >= N + 2 || nc < 0 || nc >= M + 2) continue;
				if(matrix[nr][nc] == '#') continue;
				matrix[nr][nc] = '#';
				q.offer(new int[] {nr, nc});
			}
		}
	}
	
	static int[] countSheepWolf(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc});
		int wolfCnt = 0;
		int sheepCnt = 0;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			int r = temp[0], c = temp[1];
			if(matrix[r][c] == 'v') wolfCnt+=1;
			else if(matrix[r][c] == 'o') sheepCnt += 1;
			matrix[r][c] = '#';
			for(int[] dir : new int[][] {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}) {
				int nr = r + dir[0];
				int nc = c + dir[1];
				
				if(nr < 1 || nr >= N+1 || nc < 1 || nc >= M + 1) continue;
				if(matrix[nr][nc] == '#') continue;
				q.offer(new int[] {nr, nc});
			}
		}
		
		int[] ret = new int[2];
		if(wolfCnt < sheepCnt) {
			ret[0] = sheepCnt;
		}else if(wolfCnt >= sheepCnt) {
			ret[1] = wolfCnt;
		}
		return ret;
	}
	
	
	
	
}