글 읽기 - C++) 구슬탈출2 (궁금한 질문 2가지)

woogie 3년 전 0

안녕하세요 힌트를 얻어서 문제를 풀었으나 이해안가는 부분이 있어서 질문 드립니다.

질문 부분은 코드에 주석으로

//질문1 //질문2 표시했습니다.

첫번째 질문 입니다.

//질문1에 빨간구슬을 while문으로 한방향으로 움직이고 멈출때까지 움직이는 코드 입니다.

if(map[next_ry][next_rx] != '#' && map[next_ry][next_rx] != 'O') 이후

else에서 다음좌표가 벽일때 이미 if문에 다음좌표가 저장되어 있으니

단순히 break를 써서 빠져나오면 되지 않나요?

다음 코드가 왜 있어야 하는지 모르겠습니다...

next_by -= directY[dir]; next_bx -= directX[dir];

단순히 빼보니 답이 틀리더군요 ㅠ

두번째 질문 입니다.

//질문2에 빨간구슬과 파란구슬이 같은 위치에 있을 경우 예외처리 부분 입니다.

처음에 좌표로 같다고 하기 위해 map[next_ry][next_rx] == map[next_by][next_bx]으로 했으나 틀리게 나오더군요

이 코드가

next_ry == next_by && next_rx == next_bx

와 같은 의미 아닌가요?

도움 주시면 감사하겠습니다!

#include<iostream>
#include<queue>

using namespace std;

struct INFO {
  int rx,ry,bx,by,count;
};

INFO start;
int n,m;
char map[10][11];
int visited[11][11][11][11];

int directX[] = {-1,1,0,0};
int directY[] = {0,0,-1,1};

int bfs() {

  queue<INFO> q;
  q.push(start);
  visited[start.ry][start.rx][start.by][start.bx] = 1;

  int ret = -1;

  while(!q.empty()) {
    INFO cur = q.front();
    q.pop();

    if(cur.count > 10) {break;}
    if(map[cur.ry][cur.rx] == 'O' && map[cur.by][cur.bx] != 'O') {
      ret = cur.count;
      break;
    }

    for(int dir=0; dir<4; dir++) {
      int next_ry = cur.ry;
      int next_rx = cur.rx;
      int next_by = cur.by;
      int next_bx = cur.bx;

      while(1) {
        if(map[next_ry][next_rx] != '#' && map[next_ry][next_rx] != 'O') {
          next_ry += directY[dir];
          next_rx += directX[dir];
        } else {
          //질문 1
          //이 부분 넘 헷갈린다
          //단순히 if(map[next_ry][next_rx] == '#' break; 하면 안되나요?
          if(map[next_ry][next_rx] == '#') {
            next_ry -= directY[dir];
            next_rx -= directX[dir];
          }
          break;
        }
      }

      while(1) {
        if(map[next_by][next_bx] != '#' && map[next_by][next_bx] != 'O') {
          next_by += directY[dir];
          next_bx += directX[dir];
        } else {
          //이 부분 넘 헷갈린다
          //단순히 if(map[next_ry][next_rx] == '#' break; 하면 안되나요?
          if(map[next_by][next_bx] == '#') {
            next_by -= directY[dir];
            next_bx -= directX[dir];
          }
          break;
        }
      }
      
      //질문2    
      //예외처리) 빨간색 파란색 같은 위치일때
      //map[next_ry][next_rx] == map[next_by][next_bx] 와 같은 말 아닌가?
      if(next_ry == next_by && next_rx == next_bx && map[next_ry][next_rx] != 'O') {
        int r_dist = abs(next_ry - cur.ry) + abs(next_rx - cur.rx);
        int b_dist = abs(next_by - cur.by) + abs(next_bx - cur.bx); 
        if(r_dist > b_dist) {
          next_ry -= directY[dir];
          next_rx -= directX[dir];
        } else {
            next_by -= directY[dir];
            next_bx -= directX[dir];
        }
      }

      if(!visited[next_ry][next_rx][next_by][next_bx]) {
        visited[next_ry][next_rx][next_by][next_bx] = 1;
        INFO next;
        next.ry = next_ry;
        next.rx = next_rx;
        next.by = next_by;
        next.bx = next_bx;
        next.count = cur.count + 1;
        q.push(next);
      }   
    }
  }
  return ret;
}

int main() {

  cin >> n >> m;

  for(int y=0; y<n; y++) {
    for(int x=0; x<m; x++) {
      cin >> map[y][x];

      if(map[y][x]=='R') {
        start.rx = x;
        start.ry = y;
      }
      if(map[y][x]=='B') {
        start.bx = x;
        start.by = y;
      }
    }
  }
  
  start.count = 0;

  int ret = bfs();
  cout << ret << endl;

  return 0;
}

asker5325 3년 전 1

질문 1)

break로 처리하고 공이 아래와 같은 상태로 있을 때

# # #

# R #

# B #

# # #

공이 위로 올라가게 기울인다면 76번 째 줄 직전의 상태는

# (R,B) #

# . #

# # #

로 됩니다. 이 때 파란 공이 이동한 거리가 더 크니 83번 째 줄을 수행하여

# R #

# B #

# . #

# # #

상태가 되고 이 상태가 큐에 들어가게 됩니다. 이는 실제론 불가능한 상황이므로 오답을 낼 수 있다고 생각됩니다.

질문 2)

질문 1)에서 제시했던 초기상태를 봤을 때, 오른쪽으로 굴러가게 기울인다면 공은 서로 다른 위치에 있지만 (map[next_ry][next_rx] == map[next_by][next_bx]) 값은 true를 반환하게 됩니다.

woogie 3년 전 0

그동안 정신없어서 지금 확인했네요 ㅠ

깔끔한 답변 감사합니다 ! 제대로 알고갑니다 !

다시 열심히 시작해야겠어요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++) 구슬탈출2 (궁금한 질문 2가지)

woogie 3년 전 0

asker5325 3년 전 1

질문 1)

질문 2)

woogie 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말