[BOJ 15653] 구슬 탈출4 (Java)

BOJ 15653 구슬 탈출4

문제풀이

방문체크에 대해서 다시 한번 생각하게 된 문제였다. 처음에는 빨간구슬과 파란구슬에 대한 방문체크를 따로 진행해주면 되겠지라고 생각하며 visited[구슬종류][행][열]을 생각하게 되었는데 정확하게 이전에 방문한 것을 체크하지 못했다. 몇번을 틀리고 나서야 방문한 것을 정확하게 체크하려면 두 구슬의 위치가 동시에 정확하게 같아야한다고 생각하게 되었고 visited[빨간구슬 행][빨간구슬 열][파란구슬 행][파란구슬 열]과 같이 만들어 방문체크를 하게 되었다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Node {
		int r, c, time;
		char type;

		Node(int r, int c, char type, int time) {
			this.r = r;
			this.c = c;
			this.type = type;
			this.time = time;
		}
	}

	static Queue<Node> q;
	static boolean[][][][] visited;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static char[][] map;
	static int blueR, blueC, redR, redC;
	static int N, M;

	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());
	
		q = new LinkedList<>();
		visited = new boolean[N][M][N][M];
		map = new char[N][M];
		
		for(int r = 0 ; r < N ; ++r) {
			char[] line = br.readLine().toCharArray();
			for(int c = 0 ; c < M ; ++c) {
				if(line[c] == 'R') {
					map[r][c] = '.';
					redR = r;
					redC= c;
					q.offer(new Node(r, c, line[c], 0));
				} else if(line[c] == 'B') {
					map[r][c] = '.';
					blueR = r;
					blueC = c;
					q.offer(new Node(r, c, line[c], 0));
				}else {
					map[r][c] = line[c];
				}
			}
		}

		visited[redR][redC][blueR][blueC] = true;
		
		System.out.println(bfs());
	}

	private static int bfs() {
		while(!q.isEmpty()) {
			Node blue, red;
			if(q.peek().type == 'B') {
				blue = q.poll();
				red = q.poll();
			} else {
				red = q.poll();
				blue = q.poll();
			}
			
			boolean blueInHole, redInHole, afterRed;
			int bcr, bcc, rcr, rcc;
			int bnr, bnc, rnr, rnc;
			for(int d = 0 ; d < 4 ; ++d) {
				blueInHole = redInHole = afterRed = false;
				bcr = blue.r;
				bcc = blue.c;
				rcr = red.r;
				rcc = red.c;
				
				// 파랑 구슬 이동 
				while(true) {
					bnr = bcr + dir[d][0];
					bnc = bcc + dir[d][1];
					if(bnr == rcr && bnc == rcc) afterRed = true;
					if(map[bnr][bnc] == '#') break;
					if(map[bnr][bnc] == 'O') {
						blueInHole = true;
						break;
					}
					bcr = bnr;
					bcc = bnc;
				}
				
				// 빨강 구슬 이동 
				while(true) {
					rnr = rcr + dir[d][0];
					rnc = rcc + dir[d][1];
					if(map[rnr][rnc] == '#') break;
					if(map[rnr][rnc] == 'O') {
						redInHole = true;
						break;
					}
					rcr = rnr;
					rcc = rnc;
				}
				
				// 파란구슬이 들어갔을 때 
				if(blueInHole) continue;
				// 빨간구슬이 들어갔을 때 
				if(redInHole) return red.time + 1;
				
				// 구슬이 겹쳤을 때 
				if(bcr == rcr && bcc == rcc) {
					// 빨간구슬 다음에 파란구슬이 올 때 
					if(afterRed) {
						bcr -= dir[d][0];
						bcc -= dir[d][1];
					// 파란구슬 다음에 빨간구슬이 올 때 
					} else {
						rcr -= dir[d][0];
						rcc -= dir[d][1];
					}
				}
				// 방문체크 
				if(visited[rcr][rcc][bcr][bcc]) continue;
				visited[rcr][rcc][bcr][bcc] = true;
				
				q.offer(new Node(bcr, bcc, 'B', blue.time + 1));
				q.offer(new Node(rcr, rcc, 'R', red.time + 1));
			}
		}
		
		return -1;
	}
}