728x90
삼성 SW 역량 문제.
방향이 4방향이니까,
한 방향에 대해서 깊히 생각해보고 구현하면 나머지는 비슷한 방법이다.
그래서 코드도 비슷하지만, 길어진 코드가 되었다.
총평
- 모든 경우의 수를 세는 dfs는 잘 구현했다.
- dfs 기저조건에서, 최솟값을 구하는 방법을 이제는 낯설어 하지 말자.
- 결국, 시뮬레이션의 디테일한 구성사항을 논리적 오류없이 구현해야하는 것이 중요했다.
- 반례들을 몇 십 차례 적용해 본 결과로 논리적 허점을 찾고, 수정하여 답을 얻었다.
- 문제였던 곳은, 빨간공과 파란공이 같은 선 상에 있을 때, 움직인 후 겹치지 않게 처리하는 부분이었다.
이 부분을 알고리즘 처음 짤 때부터, 신중히 생각하고 만들었으면, 더 좋았을 것 같다.
#include <cstdio>
int N, M;
char a[10][10];
int order[10];
const int max_cnt = 10;
const int INF = 11;
int ans = INF;
struct Ball{
int x, y;
};
Ball red, blue;
Ball ori_red, ori_blue;
bool red_goal, blue_goal;
void printOrder(){
for (int i=0; i<max_cnt; ++i){
printf("%d ", order[i]);
}
puts("");
}
int get_minimum_tilt_count(){
red.x = ori_red.x; red.y = ori_red.y;
blue.x = ori_blue.x; blue.y = ori_blue.y;
red_goal = false; blue_goal = false;
for (int step=0; step<max_cnt; ++step){
// up
if (order[step] == 0){
bool blueFirst = false, sameline = false;
if (blue.y == red.y) {
sameline = true;
if (blue.x > red.x) blueFirst = true;
}
// blue
int col = blue.y;
for (int i=blue.x - 1; i>=0; --i){
if (a[i][col] == '#') {blue.x = i + 1; break;}
else if (a[i][col] == 'O') {blue_goal = true; break;}
}
// red
col = red.y;
for (int i=red.x - 1; i>=0; --i){
if (a[i][col] == '#') {red.x = i + 1; break;}
else if (a[i][col] == 'O') {red_goal = true; break;}
}
if (blue.x == red.x && sameline){
if (blueFirst) ++blue.x;
else ++red.x;
}
}
// down
else if (order[step] == 1){
bool blueFirst = false, sameline = false;
if (blue.y == red.y){
sameline = true;
if (blue.x > red.x) blueFirst = true;
}
// blue
int col = blue.y;
for (int i=blue.x + 1; i<N; ++i){
if (a[i][col] == '#') {blue.x = i - 1; break;}
else if (a[i][col] == 'O') {blue_goal = true; break;}
}
// red
col = red.y;
for (int i=red.x + 1; i<N; ++i){
if (a[i][col] == '#') {red.x = i - 1; break;}
else if (a[i][col] == 'O') {red_goal = true; break;}
}
if (blue.x == red.x && sameline){
if (blueFirst) --red.x;
else --blue.x;
}
}
// left
else if (order[step] == 2){
bool blueFirst = false, sameline = false;
if (blue.x == red.x) {
sameline = true;
if (blue.y > red.y) blueFirst = true;
}
// blue
int row = blue.x;
for (int j=blue.y - 1; j>=0; --j){
if (a[row][j] == '#') {blue.y = j + 1; break;}
else if (a[row][j] == 'O') {blue_goal = true; break;}
}
// red
row = red.x;
for (int j=red.y - 1; j>=0; --j){
if (a[row][j] == '#') {red.y = j + 1; break;}
else if (a[row][j] == 'O') {red_goal = true; break;}
}
if (blue.y == red.y && sameline) {
if (blueFirst) ++blue.y;
else ++red.y;
}
}
// right
else if (order[step] == 3) {
bool blueFirst = false, sameline = false;
if (blue.x == red.x) {
sameline = true;
if (blue.y > red.y) blueFirst = true;
}
// blue
int row = blue.x;
for (int j=blue.y + 1; j<M; ++j){
if (a[row][j] == '#') {blue.y = j - 1; break;}
else if (a[row][j] == 'O') {blue_goal = true; break;}
}
// red
row = red.x;
for (int j=red.y + 1; j<M; ++j){
if (a[row][j] == '#') {red.y = j - 1; break;}
else if (a[row][j] == 'O') {red_goal = true; break;}
}
if (blue.y == red.y && sameline) {
if (blueFirst) --red.y;
else --blue.y;
}
}
if (blue_goal) {
return INF;
}
else if (red_goal) {
return step + 1;
}
}
return INF;
}
void dfs(int depth){
if (depth == max_cnt){
int min_step = get_minimum_tilt_count();
// printOrder();
// printf("ans(%d)\n", ans);
if (ans > min_step ) ans = min_step;
return;
}
for (int i=0; i<4; ++i){
if (order[depth - 1] != i){
order[depth] = i;
dfs(depth + 1);
}
}
}
void gameStart(){
for (int i=0; i<4; ++i){
order[0] = i;
dfs(1);
}
}
int main() {
scanf("%d %d", &N, &M);
for (int i=0; i<N; ++i){
char str[12];
scanf("%s", str);
for (int j=0; j<M; ++j){
a[i][j] = str[j];
if (a[i][j] == 'R'){
ori_red.x = i; ori_red.y = j; a[i][j] = '.';
}
else if (a[i][j] == 'B'){
ori_blue.x = i; ori_blue.y = j; a[i][j] = '.';
}
}
}
gameStart();
if (ans == INF) puts("-1");
else printf("%d\n", ans);
return 0;
}
728x90
'알고리즘, 자료구조 > 알고리즘 문제' 카테고리의 다른 글
[SW역량] 14501. 퇴사 (1801) | 2019.10.19 |
---|---|
16236 아기상어 (0) | 2019.09.29 |
16234. 인구이동 (0) | 2019.09.28 |
17143. 낚시왕 (0) | 2019.09.24 |
14889. 스타트와 링크 (0) | 2019.09.21 |
댓글