[백준] 18809 Gaaaaaaaaaarden #JAVA #백트래킹 #bfs

[백준] 18809 Gaaaaaaaaaarden #JAVA #백트래킹 #bfs

 

---

 

오랜 시간이 걸려서 풀었던 문제.

 

 

코드

---

import java.io.*;
import java.util.*;

public class Main {

	static List<int[]> baeyang;
	static int N,M,G,R;
	
	static int[][] garden;
	static int[] selectBaeyang;
	static int[] selectGR;
	static boolean[] isUsedBaeyang;
	static int[] spotG, spotR;
	
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	
	static int max = 0;
	
	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()); //y
		M = Integer.parseInt(st.nextToken()); //x
		G = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		
		garden = new int[N][M];

		
		// 0 - 호수, 못들어가는 땅
		// 1 - 배양액, 배양액을 뿌릴 수 없는 땅
		// 2 - 배양액을 뿌릴 수 있는 땅

		
		baeyang = new ArrayList<int[]>();
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				garden[i][j] = Integer.parseInt(st.nextToken());
				
				if(garden[i][j] == 2) {
					baeyang.add(new int[] {j,i}); //x,y
				}
			}
			
		}
		
		isUsedBaeyang = new boolean[baeyang.size()];
		spotG = new int[G];
		spotR = new int[R];
		
		Arrays.fill(spotG, -1);
		Arrays.fill(spotR, -1);
		
		findSpotG(0);
		
		System.out.println(max);
	}
	
	/**
	 * G 배양액 좌표를 백트래킹으로 구한다.
	 */
	static void findSpotG(int k) {
		if(k == G) {
			findSpotR(0); // G 배양액 좌표를 다 구하면, R 배양액 좌표를 구한다.
			return;
		}
		
		for (int i = 0; i < baeyang.size(); i++) {
			if(isUsedBaeyang[i]) continue;
			if(k > 0 && spotG[k-1] > i) continue;
			isUsedBaeyang[i] = true;
			spotG[k] = i;
			findSpotG(k+1);
			spotG[k] = -1;
			isUsedBaeyang[i] = false;
			
		}
	}
	
	/**
	 * R 배양액 좌표를 구한다.
	 */
	static void findSpotR(int k) {
		if(k == R) {
			bfs(); //G,R 배양액의 좌표를 가지고 BFS를 통해 꽃의 개수를 구한다.
			return;
		}
		
		for (int i = 0; i < baeyang.size(); i++) {
			if(isUsedBaeyang[i]) continue;
			if(k > 0 && spotR[k-1] > i) continue;
			isUsedBaeyang[i] = true;
			spotR[k] = i;
			findSpotR(k+1);
			spotR[k] = -1;
			isUsedBaeyang[i] = false;
			
		}
	}
	
	static void bfs() {
		int flower = 0;
		int[][] dist = new int[N][M];
		char[][] flw = new char[N][M];
		
		Queue<int[]> Q = new LinkedList<int[]>();
		
		for (int g : spotG) {
			int tmp[] = baeyang.get(g);
			int x = tmp[0];
			int y = tmp[1];
			
			flw[y][x] = 'G';
			dist[y][x] = 1;
			Q.add(new int[] {x,y, 0, 1}); // , G/R ,time;
		}
		
		for (int r : spotR) {
			int tmp[] = baeyang.get(r);
			int x = tmp[0];
			int y = tmp[1];
			
			flw[y][x] = 'R';
			dist[y][x] = 1;
			Q.add(new int[] {x,y, 1, 1});
		}
		
		// 0 - 호수, 못들어가는 땅
		// 1 - 배양액, 배양액을 뿌릴 수 없는 땅
		// 2 - 배양액을 뿌릴 수 있는 땅

			
		//초록 배양액 bfs
		while (!Q.isEmpty()) {
			int[] cur = Q.poll(); //x,y
			int x = cur[0];
			int y = cur[1];
			char color = cur[2] == 0 ? 'G' : 'R'; //G:0 , R:1
			int time = cur[3];
			
			if(flw[y][x] == 'F') continue; //중요! : 이미 큐에 들어온 좌표가 꽃이 되는 경우가 있다.
			
			for (int k = 0; k < 4; k++) {
				int nx = dx[k] + x;
				int ny = dy[k] + y;
				
				if(nx<0 || ny<0 || nx>= M || ny >= N) continue;
				if(garden[ny][nx] == 0) {
					flw[ny][nx] = 'h';
					continue; //호수
				}
				if(flw[ny][nx] == 'F') continue; //이미 꽃이 피었다.
				if(flw[ny][nx] == color) continue; //같은 색상의 배양액
					
				//다른 색상의 배양색을 만날경우
				if(((color == 'G' && flw[ny][nx] == 'R')) || (color == 'R' && flw[ny][nx] == 'G')) {
					if(dist[ny][nx] == time+1) {
						flw[ny][nx] = 'F';
						flower++;
					}
					continue;
				}
				
				flw[ny][nx] = color;
				dist[ny][nx] = time+1;
				
				Q.add(new int[] {nx,ny, cur[2], time+1}); //x,y
			}
		}
		
		max = Math.max(flower, max);
		
		
	}

}

 

 

풀이

---

1. 먼저 배양액이 뿌려질 수 있는 좌표의 조합을 구한다.
   • 백트래킹을 사용하여 G의 좌표를 구하고, 다음으로 R의 좌표를 구했다.
2. 좌표를 구한 뒤 BFS를 이용하여 꽃이 피는 개수를 구한다.
   • 큐에 {x좌표, y좌표, 배양액컬러, 시간} 을 넣는다. (문제와 다르게 시간은 1부터 시작하는 것으로 했다.)
   • 큐에서 꺼낸 현재 좌표가 꽃인지 체크한다.
   • 조건에 맞는 좌표를 다시 큐에 삽입한다.
     • 방문 좌표가 호수인지 체크
     • 방문 좌표가 꽃이 피었는지 체크
     • 방문 좌표가 같은 색상의 배양액이 방문했는지 체크
     • 방문 좌표가 다른 생상의 배양액이 방문했는지 체크 -> 방문 시간이 같으면 꽃을 피움

 

주의 사항

---

• 큐에서 꺼낸 현재 좌표가 꽃인지 체크한다.
  • 위 조건 때문에 계속 틀렸었다. G가 방문하고 새로운 좌표를 큐에 넣게 된다. 그런데 R이 해당 좌표를 같은 시간에 방문하면 해당 좌표는 꽃이 된다. 즉, 큐에 들어있는 G의 좌표가 이미 꽃인 경우가 발생하게 되는데 이부분을 체크하지 못해서 계속해서 갯수가 정답보다 많이 나오는 오류에 걸렸었다.
  • 설계에서 해당 부분을 놓치게 되니, 오류를 찾기 위해 무한 디버그에 빠져버렸다.
  • 풀이 계획을 잘 세우자..

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)