13460 - c++

---

요약

판을 기울이며 빨간 구슬을 구멍으로 탈출시켜야 한다 그런데 파란 구슬도 동시에 움직이며 파란 구슬이 구멍으로 탈출하면 실패 동시에 나와도 실패

 

위의 문제 구문에서 중요한 문장이 있다면 

기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때까지이다.

구슬이 벽에 닿았을 때 기울이는 것을 멈춘다. 즉 끝까지 간다 라는 말이다. 중간에 멈추는 것이 없다.

 

---

첫 아이디어

먼저 bfs, dfs 사용을 생각했다.

bfs를 사용하면 현재 갈 수 있는 방향으로 끝까지 간다음 visit 배열에 시간을 저장하는 식으로 하려고 했으나 파란 구슬까지 함께 어떻게 같이 동시에 움직여야 할지 감이 오지 않았다.

또 파란 구슬과 빨간 구슬이 겹쳤을 때, 이런 상황을 대체 어떻게 처리해야 할지 감이 오지 않았다.

그래서 여기까지 생각하고 풀이를 봤다.

---

풀이

내가 처음에 했던 구상과 꽤나 비슷한 부분이 많았다. 하지만 구현을 못했으니 난 한 게 없다.

먼저 이분은 4차원 배열을 만들었다 

//dist[a][b][c][d]
dist[11][11][11][11]

빨간 구슬이 (a, b) 위치에 있을 때 파란 구슬이 (c, d)에 있는 경우의 수를 모두 적을 수 있다.

진짜 머리를 탁 잡았다.

어찌 이런 참신한 발상을 할 수 있단 말인가.

 

그리고 내가 위에서 고민했던 빨간 구슬과 파란 구슬을 어떻게 한 번에 움직일까 라는 문제도

// <빨간구슬 X, 빨간구슬 Y, 파란구슬 X, 파란구슬 Y>
queue<tuple<int, int, int, int>> Q

위처럼 해결했다..... 왜 난 이 생각을 못했지.... 다음에 이런 문제 나오면 생각해 내야지

 

또 구슬이 겹쳤을 경우를 이 분은 아래처럼 해결하셨다.

if((n_rx == n_bx) && (n_ry == n_by)){
	if(dir == 0) (rx > bx) ? n_bx-- : n_rx--;
	else if(dir == 1) (ry > by) ? n_by-- : n_ry--;
    else if(dir == 2) (rx > bx) ? n_rx++ : n_bx++;
	else if(dir == 3) (ry > by) ? n_ry++ : n_by++;
}

늦게 출발한 구슬을 한 칸 뒤로 보내 주는 것이다. 이 코드를 보고 경악했다. 이렇게도 할 수 있구나.(좀 오버다)

 

CODE

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, m;
int dist[11][11][11][11];
string board[11];

pair<int, int> red, blue;

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

int bfs(){
  queue<tuple<int, int, int, int>> Q;
  Q.push({red.X, red.Y, blue.X, blue.Y});
  dist[red.X][red.Y][blue.X][blue.Y] = 0;
  while(!Q.empty()){
    int rx, ry, bx, by;
    tie(rx, ry, bx, by) = Q.front(); Q.pop();
    int cnt = dist[rx][ry][bx][by];
    if(cnt >= 10)return -1;
    for(int dir = 0; dir < 4; ++dir){
      int n_rx = rx, n_ry = ry, n_bx = bx, n_by = by;
      
      //파란 구슬 끝까지 이동
      while(board[n_bx + dx[dir]][n_by + dy[dir]] == '.'){
        n_bx += dx[dir];
        n_by += dy[dir];
      }
      //만약 파란 구슬이 탈출한다면
      if(board[n_bx + dx[dir]][n_by+dy[dir]] == 'O')continue;

	  //빨간 구슬 끝까지 이동
      while(board[n_rx + dx[dir]][n_ry+dy[dir]] == '.'){
        n_rx += dx[dir];
        n_ry += dy[dir];
      }
      //만약 빨간 구슬이 탈출 한다면 정답
      if(board[n_rx+dx[dir]][n_ry+dy[dir]] == 'O')return cnt+1;

      if((n_rx == n_bx) && (n_ry == n_by)){
        if(dir == 0) (rx > bx) ? n_bx-- : n_rx--;
        else if(dir == 1) (ry > by) ? n_by-- : n_ry--;
        else if(dir == 2) (rx > bx) ? n_rx++ : n_bx++;
        else if(dir == 3) (ry > by) ? n_ry++ : n_by++;
      }

      if(dist[n_rx][n_ry][n_bx][n_by] != -1)continue;
      dist[n_rx][n_ry][n_bx][n_by] = cnt+1;
      Q.push({n_rx, n_ry, n_bx, n_by});
    }
  }
  return -1;
}

int main()
{
  //init()은 신경 안 써도됨!
  init();
  
  //dist 초기화
  for(int i =0; i < 10; ++i)
    for(int j =0;j < 10; ++j)
      for(int k = 0; k < 10; ++k)
        fill(dist[i][j][k], dist[i][j][k]+10, -1);
  
  cin >> n >> m;
  for(int i = 0; i < n; ++i){
    cin >> board[i];
    for(int j =0; j < m; ++j){
      if(board[i][j] == 'R'){
        red = {i, j};
        board[i][j] = '.';
      }
      else if(board[i][j] == 'B'){
        blue = {i, j};
        board[i][j] = '.';
      }
    }
  }
  cout << bfs();
  return 0;
}

정말 깔끔하다.

---

얻어 가야 할 것들

1. bfs에서는 전 인덱스의 값을 가지고 있으면 다음 인덱스를 확인할 수 있다는 것

2. 한 번에 이동 또는 동시에 처리해야 할 것이 있다면 queue <tuple <int, int, int, int,...., int>>를 사용하는 것

---

문제를 풀며

쉬운 문제만 풀면 뭐가 공부랴, 이렇게 어려운 문제를 풀고 모르는 게 나와야 공부지.

못 풀었다고 기죽지 말고, 풀었다고 자만하지 말자. 

새로 알게 된 아이디어 들은 나중에 다른 문제를 풀 때 쓰면 되지 이런 것도 있구나 인지하고 넘어가자! 화이텡

 

참고 : https://blog.encrypted.gg/category/%EA%B0%95%EC%A2%8C/%EC%8B%A4%EC%A0%84%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?page=3 

'강좌/실전 알고리즘' 카테고리의 글 목록 (3 Page)