문제

BOJ 13460, 구슬 탈출 2

핵심

• 입력의 크기가 $10^2$이라 구현에 초점을 맞춘다.
• 빨간 구슬과 파란 구슬이 있는 보드판에서 상, 하, 좌, 우 방향으로 기울여 빨간 구슬을 구멍에 빠뜨리는 게임이다. 파란 구슬이 구멍에 빠지면 안 되고, 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져서도 안 된다. 10번 이하로 움직여서 구멍을 통해 빨간 구슬을 꺼낼 수 없으면 -1을 출력한다. 꺼낼 수 있으면 최소 몇 번 만에 꺼낼 수 있는지 구해야 한다.
• 문제를 직관적으로 접근할 때 10번 기울일 수 있는 모든 방향을 구하고 ($4^{10}$), 최대 길이가 10인 보드판에서 빨간 구슬과 파란 구슬을 움직이면 ($10^2$) 최악의 경우 대략 1억 회 정도의 연산을 하게 된다. 여기서 추가로 부가적인 연산이 있을 테니, 시간제한이 간당간당한다고 생각하며 접근하였다.
• 무엇보다도 구슬을 처리하는 부분이 문제였다. 빨간 구슬과 파란 구슬을 각각 기울이고, 겹쳤다면 기울이는 방향에 따라 출발 지점을 보고 도착 지점을 결정하는 식으로 구현하였다. 북쪽으로 기울일 때 빨간 구슬과 파란 구슬이 겹쳤다면 더 아래에서 출발한 공을 한 칸 내려주는 식으로 나머지 방향에도 비슷하게 적용하였다.

// 빨간 구슬 출발
while (board[ry + dy[dir]][rx + dx[dir]] == '.') {
	ry += dy[dir];
	rx += dx[dir];
}
// 파란 구슬 출발
while (board[by + dy[dir]][bx + dx[dir]] == '.') {
	by += dy[dir];
	bx += dx[dir];
}
// 더 이상 움직일 수 없고 빨간 구슬과 파란 구슬이 겹쳤을 때 처리
if (board[ry + dy[dir]][rx + dx[dir]] == '#'
		&& board[by + dy[dir]][bx + dx[dir]] == '#') {
	if (ry == by && rx == bx) {
		if (dir == 0)
			(r.first < b.first) ? ++by : ++ry;
		else if (dir == 1) 
			(r.second < b.second) ? --rx : --bx;
		else if (dir == 2)
			(r.first < b.first) ? --ry : --by;
		else 
			(r.second < b.second) ? ++bx : ++rx;
	}
	r = {ry, rx};
	b = {by, bx};
}

• 기본적인 접근 방법은 아래와 같다.
  1. DFS를 통해 10번의 시도를 한 경우 모든 방향의 경우를 구한다. ($4^{10}$)
  2. 10개의 방향으로 하나씩 기울인다. 공이 벽에 부딪힐 때까지 기울여서 만약 두 공의 위치가 겹친다면 출발 방향을 기준으로 더 뒤에 출발한 공을 한 칸 뒤로 움직인다.
  3. 파란 공이 도착했다면 실패로 처리한다.
  4. 빨간 공이 도착하고, 파란 공이 도착하지 않았을 경우에만 성공으로 처리하여 거리를 갱신한다.

// 파란 구슬이 도착한 경우 실패이고, 더 방향을 탐색할 필요 없으므로 isEnd = true
if (board[by + dy[dir]][bx + dx[dir]] == 'o')
	isEnd = true;
// 빨간 구슬이 도착하고, 파란 공이 도착하지 않았을 때는 성공이므로 최소 거리 갱신, 더 탐색할 필요 없으므로 isEnd = true;
if (board[ry + dy[dir]][rx + dx[dir]] == 'o') {
	if (isEnd)
		continue;
	isEnd = true;
	ans = min(ans, i + 1);
}

개선

• 파란 구슬과 빨간 구슬이 도착했을 경우 더 탐색하지 않기 위해 isEnd 변수를 사용하였다. 여전히 비효율적인 부분이 있는데, 이는 같은 방향으로 연속적으로 밀 경우 한 번만 처리해도 되는 것이다. 이미 북쪽으로 기울여 벽에 닿았는데 또 북쪽으로 밀 필요는 없으므로 연속적인 방향에 대해선 무시하는 작업이 필요하다.
• 추가로 이미 최단 거리가 5인 답이 결정되었다면, 5 이상 탐색할 필요는 없다. 최적화 작업은 아래와 같이 하였다. 전체 코드는 제일 아래에 있다.

// 10개의 방향 정보를 담은 순열 seq를 하나씩 확인한다 
int dir = seq[i];
// 앞에 방향과 같다면 처리하지 않고 건너뛴다.
if (i != 0 && seq[i] == seq[i - 1]) 
	continue;
// 파란 구슬이나 빨간 구슬이 도착했거나 최단 거리 이상 탐색할 경우 중단한다.
if (isEnd || (i + 1) >= ans)
	break; 

• 최단 거리를 구하는 효율적인 방법은 DFS보단 BFS를 이용하는 것이 효율적이다. BFS는 찾는 순간 최단 거리임을 인지할 수 있기 때문이다. 그런데도 DFS로 구현한 이유는 빨간 공과 파란 공 위치를 방향에 따라 기울인 결과를 어떻게 저장할지 까다롭다고 생각했기 때문이다. 사실 빨간 공과 파란 공의 위치를 확정하는 부분이 까다롭지, BFS를 실행하는 부분은 크게 까다로운 부분이 아니었다. 빨간 공과 파란 공 y, x 좌표 각각을 저장한 큐를 선언하고 해당 좌표에 도달하기 까지 걸린 횟수를 dist 배열에 저장하면 쉽게 해결할 수 있다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int n, m;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
string board[14];
int dist[14][14][14][14];
pair<int, int> red, blue;
int bfs() {
	queue<tuple<int, int, int, int>> q;
	q.push({red.first, red.second, blue.first, blue.second});
	dist[red.first][red.second][blue.first][blue.second] = 0;
	while (!q.empty()) {
		auto [ry, rx, by, bx] = q.front();
		q.pop();
		int cnt = dist[ry][rx][by][bx];
		if (cnt >= 10)
			return -1;
		for (int dir = 0; dir < 4; ++dir) {
			int rry = ry, rrx = rx, bby = by, bbx = bx;
			while (board[bby + dy[dir]][bbx + dx[dir]] == '.') {
				bby += dy[dir];
				bbx += dx[dir];
			}
			if (board[bby + dy[dir]][bbx + dx[dir]] == 'O')
				continue;
			while (board[rry + dy[dir]][rrx + dx[dir]] == '.') {
				rry += dy[dir];
				rrx += dx[dir];
			}
			if (board[rry + dy[dir]][rrx + dx[dir]] == 'O')
				return cnt + 1;
			if (board[rry + dy[dir]][rrx + dx[dir]] == '#'
					&& board[bby + dy[dir]][bbx + dx[dir]] == '#') {
				if (rry == bby && rrx == bbx) {
					if (dir == 0)
						(ry < by) ? ++bby : ++rry;
					else if (dir == 1) 
						(rx < bx) ? --rrx : --bbx;
					else if (dir == 2)
						(ry < by) ? --rry : --bby;
					else 
						(rx < bx) ? ++bbx : ++rrx;
				}
			}
			if (dist[rry][rrx][bby][bbx] != -1)
				continue;
			dist[rry][rrx][bby][bbx] = cnt + 1;
			q.push({rry, rrx, bby, bbx});
		}	
	}
	return -1;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);	
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> board[i];
		for (int j = 0; j < m; ++j) {
			if (board[i][j] == 'R') {
				board[i][j] = '.';
				red = {i, j};
			}
			else if (board[i][j] == 'B') {
				board[i][j] = '.';
				blue = {i, j};
			}
		}
	}
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			for (int k = 0; k < 10; ++k) {
				fill(dist[i][j][k], dist[i][j][k] + 10, -1);
			}
		}
	}
	cout << bfs();
}

• 시간복잡도 $O(4 \times n^2 \times m^2 * (n + m))$

코드

시간복잡도

• $O(4^{10} \times 10 \times n \times m)$

C++

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
string board[14];
pair<int, int> red, blue;
int ans = 1e9;
int cnt = 0;
void dfs(int depth, vector<int>& seq) {
	if (depth == 10) {
		pair<int, int> r = red;
		pair<int, int> b = blue;
		bool isEnd = false;
		for (int i = 0; i < (int)seq.size(); ++i) {
			int dir = seq[i];
			if (i != 0 && seq[i] == seq[i - 1])
				continue;
			if (isEnd || (i + 1) >= ans)
				break; 
			auto [ry, rx] = r;
			auto [by, bx] = b;
			while (board[ry + dy[dir]][rx + dx[dir]] == '.') {
				ry += dy[dir];
				rx += dx[dir];
			}
			while (board[by + dy[dir]][bx + dx[dir]] == '.') {
				by += dy[dir];
				bx += dx[dir];
			}
			if (board[ry + dy[dir]][rx + dx[dir]] == '#'
					&& board[by + dy[dir]][bx + dx[dir]] == '#') {
				if (ry == by && rx == bx) {
					if (dir == 0)
						(r.first < b.first) ? ++by : ++ry;
					else if (dir == 1) 
						(r.second < b.second) ? --rx : --bx;
					else if (dir == 2)
						(r.first < b.first) ? --ry : --by;
					else 
						(r.second < b.second) ? ++bx : ++rx;
				}
				r = {ry, rx};
				b = {by, bx};
			}
			if (board[by + dy[dir]][bx + dx[dir]] == 'O')
				isEnd = true;
			if (board[ry + dy[dir]][rx + dx[dir]] == 'O') {
				if (isEnd)
					continue;
				isEnd = true;
				ans = min(ans, i + 1);
			}
		}
		return ;
	}
	for (int dir = 0; dir < 4; ++dir) {
		seq.push_back(dir);
		dfs(depth + 1, seq);
		seq.pop_back();	
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);	
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> board[i];
		for (int j = 0; j < m; ++j) {
			if (board[i][j] == 'R') {
				board[i][j] = '.';
				red = {i, j};
			}
			else if (board[i][j] == 'B') {
				board[i][j] = '.';
				blue = {i, j};
			}
		}
	}
	vector<int> seq;
	dfs(0, seq);
	if (ans == 1e9)
		ans = -1;
	cout << ans;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class J13460_구슬탈출2 {
    static char[][] board = new char[14][14];
    static int[] red = {0, 0};
    static int[] blue = {0, 0};
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                char c = line.charAt(j);
                if (c == 'R') {
                    c = '.';
                    red[0] = i;
                    red[1] = j;
                } else if (c == 'B') {
                    c = '.';
                    blue[0] = i;
                    blue[1] = j;
                }
                board[i][j] = c;
            }
        }
        ArrayList<Integer> seq = new ArrayList<>();
        dfs(0, seq);
        if (ans == Integer.MAX_VALUE)
            ans = -1;
        System.out.println(ans);
        br.close();
    }

    static void dfs(int depth, ArrayList<Integer> seq) {
        if (depth == 10) {
            int[] r = red.clone();
            int[] b = blue.clone();
            boolean isEnd = false;
            for (int i = 0; i < seq.size(); i++) {
                int dir = seq.get(i);
                if (i != 0 && seq.get(i).equals(seq.get(i - 1)))
                    continue;
                if (isEnd || (i + 1) >= ans)
                    break;
                int ry = r[0];
                int rx = r[1];
                int by = b[0];
                int bx = b[1];
                while (board[ry + dy[dir]][rx + dx[dir]] == '.') {
                    ry += dy[dir];
                    rx += dx[dir];
                }
                while (board[by + dy[dir]][bx + dx[dir]] == '.') {
                    by += dy[dir];
                    bx += dx[dir];
                }
                if (board[ry + dy[dir]][rx + dx[dir]] == '#' && board[by + dy[dir]][bx + dx[dir]] == '#') {
                    if (ry == by && rx == bx) {
                        if (dir == 0) {
                            if (r[0] < b[0]) by++; else ry++;
                        } else if (dir == 1) {
                            if (r[1] < b[1]) rx--; else bx--;
                        } else if (dir == 2) {
                            if (r[0] < b[0]) ry--; else by--;
                        } else {
                            if (r[1] < b[1]) bx++; else rx++;
                        }
                    }
                    r[0] = ry;
                    r[1] = rx;
                    b[0] = by;
                    b[1] = bx;
                }
                if (board[by + dy[dir]][bx + dx[dir]] == 'O')
                    isEnd = true;
                if (board[ry + dy[dir]][rx + dx[dir]] == 'O') {
                    if (isEnd)
                        continue;
                    isEnd = true;
                    ans = Math.min(ans, i + 1);
                }
            }
            return;
        }
        for (int dir = 0; dir < 4; dir++) {
            seq.add(dir);
            dfs(depth + 1, seq);
            seq.remove(seq.size() - 1);
        }
    }
}