문제
핵심
- 5*5 크기의 판이 5개 주어진다. 구현에 초점을 맞춘다.
- 미로에서 탈출해야 한다. 판 5개를 자유롭게 쌓을 수 있으며, 판을 시계 방향 또는 반시계 방향으로 회전할 수 있다. 가장 빠르게 탈출해야 하는 경로를 구하기 위해선 판 5개를 쌓는 모든 경우를 구한 뒤 각각의 경우에서 회전할 수 있는 모든 경우를 구하여 전체 경로를 구할 수 있다. 전체 경로가 확정되었을 때는 3차원 배열에서 BFS를 하며 최단 거리를 탐색할 수 있다.
- 구현 사항은 크게 4가지로 구분할 수 있다.
- 판 5개를 쌓는 모든 경우 구하기
- 5개의 판이 시계 방향으로 0번, 1번, 2번, 3번 회전 할 때 모든 경우 구하기
- 판을 회전시키는 기능을 구현하기
- BFS를 통해 최단 거리 탐색하기
- 판 5개를 쌓는 모든 경우는 중복 없이 선택하는 순열과 같다. 중복 없이 선택하기 위해 이미 고른 판을 저장하기 위한 배열을 사용한다.
void findBoard(int depth, vector<int>& seq, vector<bool>& isSelected) {
if (depth == 5) {
vector<int> rSeq;
findRotation(0, seq, rSeq); // 회전할 수 있는 모든 경로를 구한다.
return;
}
for (int i = 0; i < 5; ++i) {
if (isSelected[i]) continue;
seq.push_back(i);
isSelected[i] = true;
findBoard(depth + 1, seq, isSelected);
seq.pop_back();
isSelected[i] = false;
}
}- 5개의 판이 시계방향으로 0번, 1번, 2번, 3번 회전할 때 모든 경우를 구하면 반시계 방향으로 회전하는 경우를 추가로 고려할 필요는 없다. 이는 중복을 허용하는 순열이므로 위의 코드보다 조금 더 단순하게 구현할 수 있다.
void findRotation(int depth, vector<int>& seq, vector<int>& rSeq) {
if (depth == 5) {
escape(seq, rSeq); // 모든 방향을 추가한 모든 경우(rSeq)를 구한 뒤 BFS를 통해 최소 탈출 거리를 구한다.
return;
}
for (int dir = 0; dir < 4; ++dir) {
rSeq.push_back(dir);
findRotation(depth + 1, seq, rSeq);
rSeq.pop_back();
}
}- 보드를 쌓는 순서를 seq 배열을 통해 확정하고, 회전 횟수가 담긴 rSeq배열을 통해 판을 하나씩 회전시킨다. 코드로 나타내면 다음과 같다.
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
for (int k = 0; k < 5; ++k)
tmp[i][j][k] = board[seq[i]][j][k];
}
}
for (int i = 0; i < 5; ++i)
rotate(i, rSeq[i]);
// 2차원 배열에서 회전할 때 행이 열로 가는 성질을 이용한다.
// inplace 회전이 아니므로 추가 배열 rTmp 사용한다.
void rotate(int index, int cnt) {
if (cnt == 0)
return;
int rTmp[5][5];
while (cnt--) {
for (int j = 0; j < 5; ++j) {
for (int k = 0; k < 5; ++k)
rTmp[j][k] = tmp[index][j][k];
}
for (int j = 0; j < 5; ++j) {
for (int k = 0; k < 5; ++k)
tmp[index][k][5 - j - 1] = rTmp[j][k];
}
}
}- 마지막으로 bfs를 통해 최단 거리를 탐색한다. z, y, x 좌표와 추가로 현재 얼마나 이동했는지 담는 cnt 변수를 저장한다. 마지막 출구에 도착했다면 최단 거리를 갱신시킨다.
queue<tuple<int, int, int, int>> q;
isVisited[0][0][0] = true;
q.push({0, 0, 0, 0});
while (!q.empty()) {
auto cur = q.front(); q.pop();
int z = get<0>(cur);
int y = get<1>(cur);
int x = get<2>(cur);
int cnt = get<3>(cur);
if (z == 4 && y == 4 && x == 4) {
ans = min(ans, cnt);
return ;
}
for (int dir = 0; dir < 6; ++dir) {
int nz = z + dz[dir];
int ny = y + dy[dir];
int nx = x + dx[dir];
if (nz < 0 || nz >= 5 || ny < 0 || ny >= 5 || nx < 0 || nx >= 5)
continue;
if (isVisited[nz][ny][nx] || tmp[nz][ny][nx] == 0)
continue;
isVisited[nz][ny][nx] = true;
q.push({nz, ny, nx, cnt + 1});
}
}개선
- bfs를 통해 최단 경로를 탐색할 때, 출발지와 도착지가 막혀있다면 탐색을 건너뛰어 시간을 단축할 수 있다. 추가로 이동 횟수가 최단 거리 횟수보다 크다면 경로를 탐색할 필요가 없으므로 종료시켜 효율적으로 구현할 수 있다.
// 탐색을 시작하기 전 판단 조건
if (tmp[0][0][0] == 0 || tmp[4][4][4] == 0)
return ;
// 경로 탐색 도중 종료 조건
if (cnt >= ans)
return ;코드
시간복잡도
C++
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int board[5][5][5];
int tmp[5][5][5];
int ans = 1e9;
int dz[] = {0, 0, 0, 0, 1, -1};
int dy[] = {-1, 0, 1, 0, 0, 0};
int dx[] = {0, 1, 0, -1, 0, 0};
void rotate(int index, int cnt) {
if (cnt == 0)
return;
int rTmp[5][5];
while (cnt--) {
for (int j = 0; j < 5; ++j) {
for (int k = 0; k < 5; ++k)
rTmp[j][k] = tmp[index][j][k];
}
for (int j = 0; j < 5; ++j) {
for (int k = 0; k < 5; ++k)
tmp[index][k][5 - j - 1] = rTmp[j][k];
}
}
}
void escape(vector<int>& seq, vector<int>& rSeq) {
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
for (int k = 0; k < 5; ++k)
tmp[i][j][k] = board[seq[i]][j][k];
}
}
for (int i = 0; i < 5; ++i)
rotate(i, rSeq[i]);
if (tmp[0][0][0] == 0 || tmp[4][4][4] == 0)
return ;
bool isVisited[5][5][5] = {};
queue<tuple<int, int, int, int>> q;
isVisited[0][0][0] = true;
q.push({0, 0, 0, 0});
while (!q.empty()) {
auto cur = q.front(); q.pop();
int z = get<0>(cur);
int y = get<1>(cur);
int x = get<2>(cur);
int cnt = get<3>(cur);
if (cnt >= ans)
return ;
if (z == 4 && y == 4 && x == 4) {
ans = min(ans, cnt);
return ;
}
for (int dir = 0; dir < 6; ++dir) {
int nz = z + dz[dir];
int ny = y + dy[dir];
int nx = x + dx[dir];
if (nz < 0 || nz >= 5 || ny < 0 || ny >= 5 || nx < 0 || nx >= 5)
continue;
if (isVisited[nz][ny][nx] || tmp[nz][ny][nx] == 0)
continue;
isVisited[nz][ny][nx] = true;
q.push({nz, ny, nx, cnt + 1});
}
}
}
void findRotation(int depth, vector<int>& seq, vector<int>& rSeq) {
if (depth == 5) {
escape(seq, rSeq);
return;
}
for (int dir = 0; dir < 4; ++dir) {
rSeq.push_back(dir);
findRotation(depth + 1, seq, rSeq);
rSeq.pop_back();
}
}
void findBoard(int depth, vector<int>& seq, vector<bool>& isSelected) {
if (depth == 5) {
vector<int> rSeq;
findRotation(0, seq, rSeq);
return;
}
for (int i = 0; i < 5; ++i) {
if (isSelected[i]) continue;
seq.push_back(i);
isSelected[i] = true;
findBoard(depth + 1, seq, isSelected);
seq.pop_back();
isSelected[i] = false;
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
for (int k = 0; k < 5; ++k)
cin >> board[i][j][k];
}
}
vector<int> seq;
vector<bool> isSelected(5, false);
findBoard(0, seq, isSelected);
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.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[][][] board = new int[5][5][5];
static int[][][] tmp = new int[5][5][5];
static int[] dz = {0, 0, 0, 0, 1, -1};
static int[] dy = {-1, 0, 1, 0, 0, 0};
static int[] dx = {0, 1, 0, -1, 0, 0};
static int ans = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int k = 0; k < 5; ++k)
board[i][j][k] = Integer.parseInt(st.nextToken());
}
}
ArrayList<Integer> seq = new ArrayList<>();
boolean[] isSelected = new boolean[5];
findBoard(0, seq, isSelected);
if (ans == Integer.MAX_VALUE)
ans = -1;
System.out.println(ans);
br.close();
}
static void findBoard(int depth, ArrayList<Integer> seq, boolean[] isSelected) {
if (depth == 5) {
ArrayList<Integer> rSeq = new ArrayList<>();
findRotation(0, seq, rSeq);
return;
}
for (int i = 0; i < 5; ++i) {
if (isSelected[i]) continue;
seq.add(i);
isSelected[i] = true;
findBoard(depth + 1, seq, isSelected);
seq.remove(seq.size() - 1);
isSelected[i] = false;
}
}
static void findRotation(int depth, ArrayList<Integer> seq, ArrayList<Integer> rSeq) {
if (depth == 5) {
escape(seq, rSeq);
return;
}
for (int dir = 0; dir < 4; ++dir) {
rSeq.add(dir);
findRotation(depth + 1, seq, rSeq);
rSeq.remove(rSeq.size() - 1);
}
}
static void escape(ArrayList<Integer> seq, ArrayList<Integer> rSeq) {
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j)
System.arraycopy(board[seq.get(i)][j], 0, tmp[i][j], 0, 5);
}
for (int i = 0; i < 5; ++i)
rotate(i, rSeq.get(i));
if (tmp[0][0][0] == 0 || tmp[4][4][4] == 0)
return;
boolean[][][] isVisited = new boolean[5][5][5];
Queue<int[]> q = new LinkedList<>();
isVisited[0][0][0] = true;
q.add(new int[]{0, 0, 0, 0});
while (!q.isEmpty()) {
int[] cur = q.poll();
int z = cur[0];
int y = cur[1];
int x = cur[2];
int cnt = cur[3];
if (cnt >= ans)
return;
if (z == 4 && y == 4 && x == 4) {
ans = Math.min(ans, cnt);
return;
}
for (int dir = 0; dir < 6; ++dir) {
int nz = z + dz[dir];
int ny = y + dy[dir];
int nx = x + dx[dir];
if (nz < 0 || nz >= 5 || ny < 0 || ny >= 5 || nx < 0 || nx >= 5)
continue;
if (isVisited[nz][ny][nx] || tmp[nz][ny][nx] == 0)
continue;
isVisited[nz][ny][nx] = true;
q.add(new int[]{nz, ny, nx, cnt + 1});
}
}
}
static void rotate(int index, Integer cnt) {
if (cnt == 0)
return;
int[][] rTmp = new int[5][5];
while (cnt-- > 0) {
for (int j = 0; j < 5; ++j)
System.arraycopy(tmp[index][j], 0, rTmp[j], 0, 5);
for (int j = 0; j < 5; ++j) {
for (int k = 0; k < 5; ++k)
tmp[index][k][5 - j - 1] = rTmp[j][k];
}
}
}
}
꾸준하게