삼성 sw 역량 테스트 - 구슬탈출2(13460번)

1. 개요

 삼성 sw 역량 테스트 기출 문제인 구술탈출2를 아래와 같은 구조로 풀어보겠습니다. 혹시나 코드 이해가 되지 않는다면 간단한 셈플 문제를 확인해 주시기 바랍니다.

2. 문제 분석

 백준 홈페이지의 문제에서 명시된 조건들은 다음과 같습니다.

    ① 목표 : 10번 이하로 움직여 빨간 구슬을 빼내야 합니다.

    ② 가로, 세로 크기는 3<N, M<10 입니다.

    ③ '.'은 빈칸, '#'은 벽, 'o'는 구멍을 뜻합니다.

    ④ 상, 하, 좌, 우로 움직일 수 있습니다.

    ⑤ 한번 움직이면 벽으로 인해 멈추거나 빠저나갈때까지 움직입니다.

    ⑥ 빨간 구슬이 먼저 빠져나가고 파란 구슬이 빠져나가도 실패입니다.

3. 소스코드

 이번 문제는 상하좌우 문제입니다. 깊이가 10이며 각 노드 자식이 4인 트리이며 DFS 경우 4의 10승번 탐색합니다.

 상하좌우 문제에서는 이름 그대로 상하좌우 변환 조건이 4가지이기 때문에 2번, 3번이 4번 반복 됩니다. 즉 상하좌우 중 하나만 구현하고 복붙 3번하고 수정 살짝만 해주면 됩니다.

 이번 구슬탈출2(상하좌우) 문제에서는 기본적으로 상하좌우 이동을 하기 위한 함수가 필요하며 그 함수로 인한 위 사진속 3번이 필요합니다. 또한 해당 문제에서는 아무 변화 없이 재귀를 발생시키면 아무런 의미가 없기 때문에 위 구조속 2번이 없습니다. 

먼저 오른쪽으로 이동하는 함수와 그에 대한 2, 3번 코드를 보겠습니다.

bool moveRight(pair<int, int> &p) { for (int i = p.second + 1; i <M; i++) { if (arr[p.first][i] == 'O') { return false; } else if (arr[p.first][i] == '.') { continue; } else { p.second = i - 1; return true; } } return true; }

bool moveRight(pair<int, int> &p)함수는 리턴값으로 구멍에 빠졌냐(끝났냐)를 확인하고 구슬의 위치를 옮기는 역활을 합니다. 여기서 파라메터 pair<int, int> p는 파란 구슬 또는 빨간 구슬의 좌표입니다. 함수를 간단히 설명하면 반복문을 통해 오른쪽 위치의 값을 비교하면서 'o'(구멍)이면 false를 리턴하고 '.'(빈공간)이면 이동, 그리고 마지막으로 '#'이면 현재 위치를 최종 위치로 저장하고 true를 리턴합니다. 

다음은 check(DFS)함수 속 오른쪽 이동에 대한 코드입니다.

누군가는 위 코드를 보고 제시한 구조와 다르다라고 말씀하시는 분이 계실것입니다. 네 맞습니다. 사실 수정하기 귀찮아서 변경하지 않았습니다. 제시된 구조를 따른다면 아래와 같이 코드를 수정해야 할것입니다.

하지만 구슬의 좌표가 전역변수가 아니고 또한 DFS함수인 check 함수의 하드 카피가 되는 파라메터로 사용되고 있기 때문에 상관 없다고 말씀드리며 기회가 된다면 나중에 수정하겠습니다.

추가적으로 구슬이 붙어 있을 수 있기 때문에 이동할 방향에 가까운 구슬부터 움직여야합니다. 따라서 3번번이 두 번 사용되었습니다.

마지막으로는 전체 코드입니다. 위의 오른쪽에 대한 코드를 복붙복붙하고 수정수정하면 완성시킬 수 있습니다.

#include <iostream> #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) using namespace std; int N, M; int result = 999999; char arr[11][11]; void check(pair<int, int>B_point, pair<int, int>R_point, int count); int main() { pair<int, int>B_point, R_point; char c; cin >> N >> M; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> c; arr[i][j] = c; if (c == 'B') { B_point = pair<int, int>(i, j); arr[i][j] = '.'; } if (c == 'R') { R_point = pair<int, int>(i, j); arr[i][j] = '.'; } } } check(B_point, R_point, 1); if (result > 10) result = -1; cout << result; return 0; } bool moveDown(pair<int, int> &p) { for (int i = p.first + 1; i < N; i++) { if (arr[i][p.second] == 'O') { return false; } else if (arr[i][p.second] == '.') { continue; } else { p.first = i - 1; return true; } } return true; } bool moveUp(pair<int, int> &p) { for (int i = p.first - 1; i >= 0; i--) { if (arr[i][p.second] == 'O') { return false; } else if (arr[i][p.second] == '.') { continue; } else { p.first = i + 1; return true; } } return true; } bool moveRight(pair<int, int> &p) { for (int i = p.second + 1; i <M; i++) { if (arr[p.first][i] == 'O') { return false; } else if (arr[p.first][i] == '.') { continue; } else { p.second = i - 1; return true; } } return true; } bool moveLeft(pair<int, int> &p) { for (int i = p.second - 1; i >= 0; i--) { if (arr[p.first][i] == 'O') { return false; } else if (arr[p.first][i] == '.') { continue; } else { p.second = i + 1; return true; } } return true; } void check(pair<int, int>B_point, pair<int, int>R_point, int count) { if (count < 11) { pair<int, int> B_tempP = B_point; pair<int, int> R_tempP = R_point; bool B_next, R_next; //Right B_next = false; R_next = false; if (B_tempP.second < R_tempP.second) { //R가 오른쪽에 있을때 R_next = moveRight(R_tempP); if (R_next) { arr[R_tempP.first][R_tempP.second] = 'R'; B_next = moveRight(B_tempP); if (B_next) check(B_tempP, R_tempP, count + 1); arr[R_tempP.first][R_tempP.second] = '.'; } else { B_next = moveRight(B_tempP); if (B_next) result = MIN(result, count); } } else { B_next = moveRight(B_tempP); if (B_next) { arr[B_tempP.first][B_tempP.second] = 'B'; R_next = moveRight(R_tempP); arr[B_tempP.first][B_tempP.second] = '.'; if (R_next) check(B_tempP, R_tempP, count + 1); else result = MIN(result, count); } } //Left B_tempP = B_point; R_tempP = R_point; B_next = false; R_next = false; if (B_tempP.second > R_tempP.second) { //R가 왼쪽에 있을때 R_next = moveLeft(R_tempP); if (R_next) { arr[R_tempP.first][R_tempP.second] = 'R'; B_next = moveLeft(B_tempP); arr[R_tempP.first][R_tempP.second] = '.'; if (B_next) check(B_tempP, R_tempP, count + 1); } else { B_next = moveLeft(B_tempP); if (B_next) result = MIN(result, count); } } else { B_next = moveLeft(B_tempP); if (B_next) { arr[B_tempP.first][B_tempP.second] = 'B'; R_next = moveLeft(R_tempP); arr[B_tempP.first][B_tempP.second] = '.'; if (R_next) check(B_tempP, R_tempP, count + 1); else result = MIN(result, count); } } //Up B_tempP = B_point; R_tempP = R_point; B_next = false; R_next = false; if (B_tempP.first > R_tempP.first) { //R가 위(작을)에 있을때 R_next = moveUp(R_tempP); if (R_next) { arr[R_tempP.first][R_tempP.second] = 'R'; B_next = moveUp(B_tempP); arr[R_tempP.first][R_tempP.second] = '.'; if (B_next) check(B_tempP, R_tempP, count + 1); } else { B_next = moveUp(B_tempP); if (B_next) result = MIN(result, count); } } else { B_next = moveUp(B_tempP); if (B_next) { arr[B_tempP.first][B_tempP.second] = 'B'; R_next = moveUp(R_tempP); arr[B_tempP.first][B_tempP.second] = '.'; if (R_next) check(B_tempP, R_tempP, count + 1); else result = MIN(result, count); } } //Down B_tempP = B_point; R_tempP = R_point; B_next = false; R_next = false; if (B_tempP.first < R_tempP.first) { //R가 아래(클)에 있을때 R_next = moveDown(R_tempP); if (R_next) { arr[R_tempP.first][R_tempP.second] = 'R'; B_next = moveDown(B_tempP); arr[R_tempP.first][R_tempP.second] = '.'; if (B_next) check(B_tempP, R_tempP, count + 1); } else { B_next = moveDown(B_tempP); if (B_next) result = MIN(result, count); } } else { B_next = moveDown(B_tempP); if (B_next) { arr[B_tempP.first][B_tempP.second] = 'B'; R_next = moveDown(R_tempP); arr[B_tempP.first][B_tempP.second] = '.'; if (R_next) check(B_tempP, R_tempP, count + 1); else result = MIN(result, count); } } } }