문제
https://www.acmicpc.net/problem/13460
풀이
풀이 자체는 완전탐색으로 접근해서 빠르게 돌아갈 줄 알았는데 디버깅 과정에서 되게 많은 시간이 걸려서 당황했다. 아마 코드가 많이 더러워서 그렇지 않나 생각해본다.
풀이는 완점탐색 + 겹치는 경우 처리를 통해 풀었다. 먼저 문제를 봤을때 공이 한개만 있으면 dp로 접근할 수 있지 않을까 생각했었는데 공이 두개인데다가 제약 조건에도 숫자가 매우 작아서 그냥 10번안에 할 수 있는 모든 행동을 하는 식으로 풀었다.
이때 벽, 구멍이 정해져 있는 경우 특정 지점에서 어떤 행동을 했을때 이동할 수 있는 위치는 정해져 있기 때문에 미리 구해서 다 저장해주고 그다음에 완전탐색을 돌면서 처리해줬다. 이때 공이 겹치는 경우를 처리해야 하는데 공이 겹치는 경우에는 이전 위치와 이전 행동을 저장해 확인하고 어떤 공을 움직여야 하는지 정해서 겹침을 없앴다.
걸린 시간 : 1시간 42분 9초
실수
- 겹침을 해소할때 기준을 이상하게 해서 한동안 애먹음
- 코드가 무거워서 디버깅에 시간이 많이 걸린 것 같음
- 이외에도 여러가지 것을 빼먹어서 고생함
- 문자열 관련 처리 함수들 공부해야 할 것 같음
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <utility>
#include <string>
using namespace std;
#define ZERO_PAIR make_pair(0, 0)
#define WALL 1
#define BLANK 0
#define RED_BALL 2
#define BLUE_BALL 3
#define HOLE 4
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4
vector<vector<int>> matrix(11, vector< int>(11, BLANK)); // 입력값을 특정한 숫자로 변환해서 저장
// 각각 자기위치에서 매트릭스 이름에 해당하는 행동을 할때 이동해야 하는 위치를 기록
vector<vector<pair<int, int>>> matrixUp(11, vector< pair<int, int>>(11, ZERO_PAIR));
vector<vector<pair<int, int>>> matrixDown(11, vector< pair<int, int>>(11, ZERO_PAIR));
vector<vector<pair<int, int>>> matrixLeft(11, vector< pair<int, int>>(11, ZERO_PAIR));
vector<vector<pair<int, int>>> matrixRight(11, vector< pair<int, int>>(11, ZERO_PAIR));
int n, m;
int prev_red_row;
int prev_red_col;
int prev_blue_row;
int prev_blue_col;
int prev_action;
void preprocessing() { // 모든 matrix에서 이동해야할 위치를 기록함.
// 더 효율적인 코드가 있지만 그다지 차이가 없어서 그냥 이렇게 작성함
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] != WALL) {
matrixUp[i][j] = make_pair(i, j);
matrixDown[i][j] = make_pair(i, j);
matrixRight[i][j] = make_pair(i, j);
matrixLeft[i][j] = make_pair(i, j);
// 처음 만나는 벽, 구멍을 저장
for (int k = 1;; k++) {
if (matrix[i + k][j] == WALL) {
matrixDown[i][j] = make_pair(i + k - 1, j);
break;
}
if (matrix[i + k][j] == HOLE) {
matrixDown[i][j] = make_pair(i + k, j);
break;
}
}
// 처음 만나는 벽, 구멍을 저장
for (int k = 1;; k++) {
if (matrix[i - k][j] == WALL) {
matrixUp[i][j] = make_pair(i - k + 1, j);
break;
}
if (matrix[i - k][j] == HOLE) {
matrixUp[i][j] = make_pair(i - k, j);
break;
}
}
// 처음 만나는 벽, 구멍을 저장
for (int k = 1;; k++) {
if (matrix[i][j + k] == WALL) {
matrixRight[i][j] = make_pair(i, j + k - 1);
break;
}
if (matrix[i][j + k] == HOLE) {
matrixRight[i][j] = make_pair(i, j + k);
break;
}
}
// 처음 만나는 벽, 구멍을 저장
for (int k = 1;; k++) {
if (matrix[i][j - k] == WALL) {
matrixLeft[i][j] = make_pair(i, j - k + 1);
break;
}
if (matrix[i][j - k] == HOLE) {
matrixLeft[i][j] = make_pair(i, j - k);
break;
}
}
}
}
}
}
int bruteForce(int red_row, int red_col, int blue_row, int blue_col, int cnt) { // 10인 지점까지 완전탐색
if (cnt > 10) {
return -1;
}
else if (matrix[blue_row][blue_col] == HOLE) {
return -1;
}
else if (matrix[red_row][red_col] == HOLE) {
if (cnt == 6) {
return cnt;
}
return cnt;
}
else if (red_row == blue_row && red_col == blue_col) { // 전도 같은 경우는 존재하지 않음
if (prev_action == UP) {
if (prev_red_row < prev_blue_row) {
blue_row += 1;
}
else {
red_row += 1;
}
}
else if (prev_action == DOWN) {
if (prev_red_row < prev_blue_row) {
red_row -= 1;
}
else {
blue_row -= 1;
}
}
else if (prev_action == RIGHT) {
if (prev_red_col < prev_blue_col) {
red_col -= 1;
}
else {
blue_col -= 1;
}
}
else if (prev_action == LEFT) {
if (prev_red_col < prev_blue_col) {
blue_col += 1;
}
else {
red_col += 1;
}
}
}
int res = 20;
int temp;
prev_red_row = red_row;
prev_red_col = red_col;
prev_blue_row = blue_row;
prev_blue_col = blue_col;
prev_action = UP;
temp = bruteForce(matrixUp[red_row][red_col].first, matrixUp[red_row][red_col].second,
matrixUp[blue_row][blue_col].first, matrixUp[blue_row][blue_col].second, cnt + 1);
if (temp != -1) {
res = min(temp, res);
}
prev_red_row = red_row;
prev_red_col = red_col;
prev_blue_row = blue_row;
prev_blue_col = blue_col;
prev_action = DOWN;
temp = bruteForce(matrixDown[red_row][red_col].first, matrixDown[red_row][red_col].second,
matrixDown[blue_row][blue_col].first, matrixDown[blue_row][blue_col].second, cnt + 1);
if (temp != -1) {
res = min(temp, res);
}
prev_red_row = red_row;
prev_red_col = red_col;
prev_blue_row = blue_row;
prev_blue_col = blue_col;
prev_action = RIGHT;
temp = bruteForce(matrixRight[red_row][red_col].first, matrixRight[red_row][red_col].second,
matrixRight[blue_row][blue_col].first, matrixRight[blue_row][blue_col].second, cnt + 1);
if (temp != -1) {
res = min(temp, res);
}
prev_red_row = red_row;
prev_red_col = red_col;
prev_blue_row = blue_row;
prev_blue_col = blue_col;
prev_action = LEFT;
temp = bruteForce(matrixLeft[red_row][red_col].first, matrixLeft[red_row][red_col].second,
matrixLeft[blue_row][blue_col].first, matrixLeft[blue_row][blue_col].second, cnt + 1);
if (temp != -1) {
res = min(temp, res);
}
if (res == 20) {
return -1;
}
if (res == 6) {
return res;
}
return res;
}
int main() {
int red_row, red_col, blue_row, blue_col;
scanf("%d %d", &n, &m);
cin.ignore();
for (int i = 0; i < n; i++) {
string temp;
getline(cin, temp);
for (int j = 0; j < m; j++) {
if (temp[j] == '#') {
matrix[i][j] = WALL;
}
else if (temp[j] == '.') {
matrix[i][j] = BLANK;
}
else if (temp[j] == 'R') {
matrix[i][j] = RED_BALL;
red_row = i, red_col = j;
}
else if (temp[j] == 'B') {
matrix[i][j] = BLUE_BALL;
blue_row = i, blue_col = j;
}
else if (temp[j] == 'O') {
matrix[i][j] = HOLE;
}
}
}
preprocessing();
printf("%d", bruteForce(red_row, red_col, blue_row, blue_col, 0));
return 0;
}
기록용 블로그