[백준 13460번] 구슬 탈출 2 C++, Java

[구슬 탈출2]
https://www.acmicpc.net/problem/13460

푸는 데 상당히 많은 시간이 걸린 BFS를 이용한 구현 문제였다. 최단거리를 구하는 문제이기에 BFS인 점은 빨리 파악했지만 구현하는데 많은 시행착오를 겪었다.

풀이 방법

1.

Pair라는 객체를 만들어 빨간 공의 좌표, 파란 공의 좌표 그리고 지금까지 굴러온 횟수를 저장한다.

2.

Queue를 생성하여 처음 시작점의 좌표를 offer하고 Queue가 비어있지 않을 동안 for문을 통해 동서남북으로 빨간 공과 파란 공을 동시에!! 굴린다. (동시에 굴리지 않고 따로 굴리게 되면 실수가 잦아질 수 있다. 필자도 그렇게 하다 실패했다.)

3.

for문으로 네 방향으로 굴리는 와중에 빨간 공과 파란 공이 각각 구멍에 들어갔는지 확인한다. 만약 파란 공이 들어갔다면 빨간 공이 들어갔는지 여부에 상관없이 실패다. 하지만 실패라고 return으로 그만두면 안 되고 continue를 통해 성공의 경우를 찾아야 한다.

4.

for문으로 굴리면서 빨간 공과 파란 공이 둘 다 구멍에 들어가지 않았다면, 4차원 boolean 배열 visited를 확인하여 방문하지 않았다면 다시 Queue에 공 두 개의 좌표와 지금까지 굴러온 횟수 + 1로 Pair 객체를 생성하여 추가해준다.

5.

굴러온 횟수가 10번이 넘어가거나, 빨간 공만 들어가는 경우가 발견되지 않은 채로 Queue가 비게 되면 -1을 출력한다. (11번만에 빨간 공만 구멍에 들어가게 될 때도 -1을 출력해야 한다는 점에 유의한다.)

Java 코드

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


public class Main {
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer str;
	//static Scanner sc = new Scanner(System.in);
	//static long BIG = (long)(Math.pow(2,63));
	static int N,M;
	static char[][] board;
	static boolean [][][][] visited;
	static int rrow,rcol,brow,bcol;
	static int[] dx = {1,0,-1,0};  // col
	static int[] dy = {0,1,0,-1};  // row
	static Queue<Pair> q = new LinkedList<> ();

	public static void main(String[] args) throws IOException {
		str = new StringTokenizer(br.readLine());
		N = Integer.parseInt(str.nextToken());
		M = Integer.parseInt(str.nextToken());
		visited = new boolean[11][11][11][11];

		board = new char[N+1][M+1];
		for(int i=0;i<N;++i) {
			String row = br.readLine();
			for(int j=0;j<M;++j) {
				if(row.charAt(j) == '#') {
					board[i+1][j+1] = '#';
				} else if(row.charAt(j) == '.') {
					board[i+1][j+1] = '.';
				} else if(row.charAt(j) == 'O') {
					board[i+1][j+1] = 'O';
				} else if(row.charAt(j) == 'R') {
					rrow = i+1;
					rcol = j+1;
					board[i+1][j+1] = 'R';
				} else {
					brow = i+1;
					bcol = j+1;
					board[i+1][j+1] = 'B';
				}
			}
		}

		bfs(rrow, rcol, brow, bcol);
		bw.flush(); bw.close();
		
	}

	public static void bfs(int rrow, int rcol, int brow, int bcol) throws IOException {
		q.offer(new Pair(rrow, rcol, brow, bcol,0));

		while(!q.isEmpty()) {
			Pair p = q.poll();
			visited[p.rrow][p.rcol][p.brow][p.bcol] = true;
			int curCnt = p.curCnt;

			if(curCnt > 10) {
				bw.write(-1 + "\n");
				return;
			}

			for(int i=0;i<4;++i) {
				boolean isRedHole = false;
				boolean isBlueHole = false;

				int nrr = p.rrow;
				int nrc = p.rcol;
				int nbr = p.brow;
				int nbc = p.bcol;

				// red bead rolls
				while(board[nrr+dy[i]][nrc+dx[i]] != '#') {  // while not '#'
					nrr += dy[i];
					nrc += dx[i];
					if(board[nrr][nrc] == 'O') { // if it is 'O'
						isRedHole = true;
						break;
					} 
				}

				// blue bead rolls
				while(board[nbr+dy[i]][nbc+dx[i]] != '#') {  // while not '#'
					nbr += dy[i];
					nbc += dx[i];
					if(board[nbr][nbc] == 'O') {  // if it is 'O'
						isBlueHole = true;
						break;
					}
				}
				
				if(isBlueHole) continue;  // blue bead is in the hole
				if(isRedHole && !isBlueHole) {  // only red bead is in the hole
					if(curCnt < 10) {
						bw.write(curCnt+1 + "\n");
						return;
					} else {
						bw.write(-1 + "\n");
						return;
					}
				}

				// both are not in the hole AND they are at the same position
				if(nrr == nbr && nrc == nbc) {
					int redDist = distance(p.rrow, p.rcol, nrr, nrc);
					int blueDist = distance(p.brow, p.bcol, nbr, nbc);

					if(redDist > blueDist) {
						nrr -= dy[i];
						nrc -= dx[i];
					} else if(redDist < blueDist) {
						nbr -= dy[i];
						nbc -= dx[i];
					}
				}

				// the positions of two beads are not visited yet, then offer to the queue
				if(!visited[nrr][nrc][nbr][nbc]) {
					q.offer(new Pair(nrr,nrc,nbr,nbc,curCnt+1));
				}

			}

		}

		bw.write(-1+"\n");
		return;
	}

	public static int distance(int row, int col, int nr, int nc) {
		return Math.abs(row - nr) + Math.abs(col - nc);
	}
}

class Pair {
	int rrow,brow;
	int rcol,bcol;
	int curCnt;

	public Pair(int rrow, int rcol, int brow, int bcol, int curCnt) {
		this.rrow = rrow;
		this.rcol = rcol;
		this.brow = brow;
		this.bcol = bcol;
		this.curCnt = curCnt;
	}
}

C++ 코드

기본적으로 풀이 방법은 같으나 Pair 객체를 따로 만들지 않고 vector를 활용하여 Queue에 넣어주는 방식으로 풀었다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int n,m;
int Rr, Rc, Br, Bc;
char board[11][11];
bool visited[11][11][11][11];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
queue< vector<int> > q;

int distance(int r, int c, int nr, int nc) {
	return abs(r-nr) + abs(c-nc);
}

void bfs(int Rr, int Rc, int Br, int Bc) {
	vector<int> pair;
	pair.push_back(Rr); pair.push_back(Rc); pair.push_back(Br); pair.push_back(Bc); pair.push_back(0);

	q.push(pair);

	while(!q.empty()) {
		vector<int> p = q.front();
		q.pop();
		visited[p[0]][p[1]][p[2]][p[3]] = true;

		int curCnt = p[4];

		for(int i=0;i<4;++i) {
			int nrr = p[0];
			int nrc = p[1];
			int nbr = p[2];
			int nbc = p[3];

			bool isRedHole = false;
			bool isBlueHole = false;

			while(board[nrr + dy[i]][nrc + dx[i]] != '#') {
				nrr += dy[i];
				nrc += dx[i];
				if(board[nrr][nrc] == 'O') {
					isRedHole = true;
					break;
				}
			}

			while(board[nbr + dy[i]][nbc + dx[i]] != '#') {
				nbr += dy[i];
				nbc += dx[i];
				if(board[nbr][nbc] == 'O') {
					isBlueHole = true;
					break;
				}
			}

			if(isBlueHole) continue;
			if(isRedHole && !isBlueHole) {
				if(curCnt < 10) {
					cout<<curCnt+1<<"\n";
					return;
				} else {
					cout<<-1<<"\n";
					return;
				}
			}

			if(nrr == nbr && nrc == nbc) {
				int redDist = distance(p[0],p[1],nrr,nrc);
				int blueDist = distance(p[2],p[3],nbr,nbc);

				if(redDist > blueDist) {
					nrr -= dy[i];
					nrc -= dx[i];
				} else if(redDist < blueDist) {
					nbr -= dy[i];
					nbc -= dx[i];
				}
			}

			if(!visited[nrr][nrc][nbr][nbc]) {
				vector<int> v;
				v.push_back(nrr); v.push_back(nrc); v.push_back(nbr); v.push_back(nbc); v.push_back(curCnt+1);
				q.push(v);
			}
		}
	}

	cout<<-1<<"\n";
	return;
}

int main(void) {
	ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	cin>>n>>m;
	for(int i=0;i<n;++i) {
		for(int j=0;j<m;++j) {
			char c;
			cin>>c;
			board[i+1][j+1] = c;
			if(c == 'R') {
				Rr = i+1;
				Rc = j+1;
			} else if(c == 'B') {
				Br = i+1;
				Bc = j+1;
			}
		}
	}

	bfs(Rr, Rc, Br, Bc);


	return 0;
}