[백준] 13460.cpp : 구슬 탈출 2

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

#include <iostream>
#include <vector>
using namespace std;

int MINI(int x, int y)
{
  return x < y ? x : y;
}

class Point
{
public:
  int x;
  int y;

  Point() { x=0; y = 0;}
  Point(int a, int b) : x(a), y(b) {}
  void Set(int a, int b) { x = a; y = b;}
};

Point Red, Blue, Hole;
int n, m, result;
char data;
vector<vector<char>> map;
int dirX[4] = {-1, 1, 0, 0}; // 방향에 대한 (x,y)
int dirY[4] = {0, 0, 1, -1};

int move(int count, Point target, Point other, int dir)
{
  // 두 공이 향할 곳이 모두 벽이라면 바로 빠져나오기
  if(map[target.x + dirX[dir]][target.y + dirY[dir]] == '#' && map[other.x + dirX[dir]][other.y + dirY[dir]] == '#') { return 11;}

  // 만약 현재까지 10번을 굴렸으면 실패했다는 뜻
  if(count == 10) { return 11;}

  // 다음 방향이 둘 다 벽이 아닐 경우 일단 해당 방향으로 옮겨줄 것임
  // 한번 굴렸음을 표시
  count++;
  // 이번 함수 내에서 사용할 위치 두개 복사해서 생성
  Point R(target.x, target.y);
  Point B(other.x, other.y);

  bool fMove = true; // 빨간공 움직이는지 상태값
  bool sMove = true; // 파란공 움직이는지 상태값
  bool redIn = false; // 빨간공 빠졌는지 상태값
  bool blueIn = false; // 파란공 빠졌는지 상태값

  // 하나라도 움직이는 중이라면 계속 움직여줘야함 (벽에 닿을 때 까지)
  while(fMove || sMove)
  {
    // 빨간공 다음위치가 벽이 아니라면 옮겨준다
    if(map[R.x + dirX[dir]][R.y + dirY[dir]] != '#')
    {
      R.x += dirX[dir];
      R.y += dirY[dir];
      fMove = true;
    }
    else fMove = false;

    // 파란공 다음위치가 벽이 아니라면 옮겨준다
    if(map[B.x + dirX[dir]][B.y + dirY[dir]] != '#')
    {
      B.x += dirX[dir];
      B.y += dirY[dir];
      sMove = true;
    }
    else sMove = false;
    // 움직이다가 도중에 구멍을 만나게 되면 처리해준다
    if(B.x == Hole.x && B.y == Hole.y) blueIn = true;
    if(R.x == Hole.x && R.y == Hole.y) redIn = true;
  }
  // 만약 다 움직였는데 중간에 파란공이 빠졌다고 처리된 경우 실패
  if(blueIn) return 11;
  // 파란공이 안빠지고 빨간공만 빠졌을 경우에 성공처리해주고 count 반환
  if(redIn) return count;

  // 두 공이 겹쳤을 경우 하나 옮겨줘야 함
  if(R.x == B.x && R.y == B.y)
  {
    // 방향에 따라서 공 하나 해당방향으로 옮겨준다
    switch (dir) {
      case 0:
        target.x < other.x ? B.x++ : R.x++;
        break;
      case 1:
        target.x > other.x ? B.x-- : R.x--;
        break;
      case 2:
        target.y > other.y ? B.y-- : R.y--;
        break;
      case 3:
        target.y < other.y ? B.y++ : R.y++;
        break;
    }
  }

  // 이번에 옮겨준 방향에 따라서 다음번 재귀호출을 통제 (이번 방향과 반대방향으로 옮겨주는것은 의미가 없기 떄문에)
  // 이번에 옮겨준 위치를 기준으로 해당 방향들을 전부 탐색
  // 재귀호출
  switch (dir) {
    case 0:
      return MINI(MINI(move(count, R, B, 0), move(count, R, B, 3)), move(count, R, B, 2));
      break;
    case 1:
      return MINI(MINI(move(count, R, B, 3), move(count, R, B, 1)), move(count, R, B, 2));
      break;
    case 2:
      return MINI(MINI(move(count, R, B, 0), move(count, R, B, 1)), move(count, R, B, 2));
      break;
    case 3:
      return MINI(MINI(move(count, R, B, 0), move(count, R, B, 1)), move(count, R, B, 3));
      break;
  }
}

int main(void)
{
  cin >> n >> m;
  for(int i = 0 ; i < n ; i++)
  {
    vector<char> line;
    for(int j = 0 ; j < m ; j++)
    {
      cin >> data;
      line.emplace_back(data);
      if(data == 'R') Red.Set(i, j);
      else if(data == 'B') Blue.Set(i, j);
      else if(data == 'O') Hole.Set(i, j);
    }
    map.emplace_back(line);
  }
  // 첫 시작점에서 상하좌우를 다 탐색하고, 그 중 최솟값을 결과로 받음
  result = MINI(MINI(MINI(move(0, Red, Blue, 0), move(0, Red, Blue, 1)), move(0, Red, Blue, 2)), move(0, Red, Blue, 3));
  // 만약 모든 방향에 있어서 불가능하다고 나오면 -1
  if(result == 11) result = -1;
  cout << result << '\n';
}

 

[Try]

1. 우선 내가 갈 수 있는 모든 방향을 재귀적으로 탐색하고 있는데, 시간이 문제가 아니라 로직 자체도 매우 꼬인다.

     골드의 벽이 너무나 높다.. 이렇게 차이가 클 줄은 몰랐다 골드 별찍기는 쉬웠는데 ㅠㅠ

     일단 다행히? 시간초과는 아닌 것 같다 틀렸습니다 가 나오니깐...

2. 반례를 찾았다!!!!!!!!!! 미쳤다!!!!!!!! 맞았다!!!!!!!!!!!!!!!!! 코드가 더럽긴 하지만 기분이 너무 좋다!!!!!!!!!!!!!!!!!!!!!!!!!!

 

[Point]

1. 뭐를 포인트라고 해야할지 모르겠다. 그냥 복잡하다

2. 다른 분들 코드 보기가 싫다 ㅜㅜ 이거 푼다고 혼이 다 빠져나갔다

 

[More]

1. 나중에 다른 분들 코드 확인할 것

2. 그래프 탐색, 너비 우선 탐색(bfs)으로 푼 것들 확인할 것