백준 13460 째로탈출 2

문제 링크입니다: https://www.acmicpc.net/problem/13460

처음에는 기존 보드판을 넘겨야한다는 것이 핵심이였습니다.

즉, 보드를 전역변수로 선언하여 계산하면 특정 테스트 케이스에서 오류가 발생합니다.

저 같은 경우는 board를 전역변수로 선언했을 때 테스트 케이스는 다 맞았는데 항상 4%에서 틀렸다고 나와서 한참을 고민했습니다.

결론을 말하자면,

6 7
#######
#..BR##
#.#####
#.#O###
#....##
#######

다음과 같은 테스트 케이스의 답은 8이지만 전역변수로 선언하여 전달하면 9가 나와 오답이 나옵니다.

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

const int MAX = 10;

 

int row, col; //가로, 세로

int minCnt = INF;

int dy[4] = { -1, 0, 0, 1 };

int dx[4] = { 0, -1, 1, 0 };

 

typedef struct

{

        int y, x;

}Coord;

 

//기울이는 방향 0:위로, 1:왼쪽, 2:오른쪽, 3:아래

void tilt(string board[MAX], int dir, int cnt, Coord R, Coord B)

{

        //기저사례

        if (++cnt > 10)

               return;

 

        string copy[MAX];

        for (int i = 0; i < col; i++)

               copy[i] = board[i]; //보드판 복사

 

        bool red = false, blue = false; //목적지에 도달했는가

        //0: R 먼저, 1: B 먼저

        int order = 0;

        switch (dir)

        {

        case 0:

               if (B.y < R.y) //B가 R보다 위에 있을 경우

                       order = 1;

               break;

        case 1:

               if (B.x < R.x) //B가 R보다 왼쪽에 있을 경우

                       order = 1;

               break;

        case 2:

               if (R.x < B.x) //B가 R보다 오른쪽에 있을 경우

                       order = 1;

               break;

        case 3:

               if (R.y < B.y) //R이 B보다 위에 있을 경우

                       order = 1;

               break;

        }

        if (order == 0) //R 먼저

        {

               while (1) //R

               {

                       int nextY = R.y + dy[dir];

                       int nextX = R.x + dx[dir];

                       if (copy[nextY][nextX] == '#') //막히면 그만 움직인다

                              break;

                       if (copy[nextY][nextX] == 'O') //목적지에 도달하면

                       {

                              copy[R.y][R.x] = '.';

                              R.y = R.x = -1;

                              red = true;

                              break;

                       }

                       copy[R.y][R.x] = '.';

                       copy[nextY][nextX] = 'R';

                       R.y = nextY;

                       R.x = nextX;

               }

               while (1) //B

               {

                       int nextY = B.y + dy[dir];

                       int nextX = B.x + dx[dir];

                       if (copy[nextY][nextX] == '#' || copy[nextY][nextX] == 'R') //R과 B는 동일선상에 있을 수 없다

                              break;

                       if (copy[nextY][nextX] == 'O')

                       {

                              copy[B.y][B.x] = '.';

                              B.y = B.x = -1;

                              blue = true;

                              break;

                       }

                       copy[B.y][B.x] = '.';

                       copy[nextY][nextX] = 'B';

                       B.y = nextY;

                       B.x = nextX;

               }

        }

        else

        {

               while (1) //B

               {

                       int nextY = B.y + dy[dir];

                       int nextX = B.x + dx[dir];

                       if (copy[nextY][nextX] == '#')

                              break;

                       if (copy[nextY][nextX] == 'O')

                       {

                              copy[B.y][B.x] = '.';

                              B.y = B.x = -1;

                              blue = true;

                              break;

                       }

                       copy[B.y][B.x] = '.';

                       copy[nextY][nextX] = 'B';

                       B.y = nextY;

                       B.x = nextX;

               }

               while (1) //R

               {

                       int nextY = R.y + dy[dir];

                       int nextX = R.x + dx[dir];

                       if (copy[nextY][nextX] == '#' || copy[nextY][nextX] == 'B')

                              break;

                       if (copy[nextY][nextX] == 'O')

                       {

                              copy[R.y][R.x] = '.';

                              R.y = R.x = -1;

                              red = true;

                              break;

                       }

                       copy[R.y][R.x] = '.';

                       copy[nextY][nextX] = 'R';

                       R.y = nextY;

                       R.x = nextX;

               }

        }

        if (blue) //파랑이 빠지면 안됨

               return;

        else if (red)

        {

               minCnt = min(cnt, minCnt);

               return;

        }

        for (int i = 0; i < 4; i++)

               //같은 방향이면 벽이므로 무의미, 반대방향이면 그 전 위치로 가므로 무의미

               if (i != dir || i != (3 - dir))

                       tilt(copy, i, cnt, R, B); //변경된 상태인 보드를 넘긴다

}

 

int main(void)

{

        Coord R, B; //Red, Blue 좌표

        string board[MAX];

        cin >> col >> row;

        if (col < 3 || col>10 || row < 3 || row>10)

               exit(-1);

 

        for (int i = 0; i < col; i++)

        {

               cin >> board[i];

               for (int j = 0; j < row; j++)

                       if (board[i][j] == 'R')

                              R.y = i, R.x = j;

                       else if (board[i][j] == 'B')

                              B.y = i, B.x = j;

        }

 

        for (int i = 0; i < 4; i++) //모든 방향 시도

               tilt(board, i, 0, R, B); //반면 여기서는 기존 보드를 넘겨야하므로 copy가 필요

 

        if (minCnt == INF)

               cout << -1 << endl;

        else

               cout << minCnt << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~