글 읽기 - 해결은 했지만 memset의 초기화 값에서 이해가 안 되는 문제가 있습니다.

jin1303 2년 전 0

일단 문제는 다익스트라 최단 경로로 해결하였습니다.

문제는 89번째 줄의 memset초기화 값을 처음에 0x3f로 진행하였더니 실패가 계속 떴습니다.

틀린 부분을 못 찾아서 이것 저것 수정해보다가 초기화 값을 0x7f로만 바꾸어주니 해결이 됬습니다.

memset이 초기화 하는 대상은 다익스트라의 시작점에서부터 밖으로 나가는데 열어야하는 문의 최소 개수입니다.

아무리 많은 문을 열어도 문제의 입력상 1만개이상의 문을 열수는 없는데

초기화 값을 0x3f에서 0x7f로만 늘려 준 것으로 왜 문제가 해결된 걸까요?

int형을 0x3f로 초기화 하면 1만보다 훨씬 큰 수 아닌가요?

#include<iostream>
#include<queue>
#include<vector>
#include<string.h>
#include<string>
using namespace std;

char prison[102][102];
int min_door[3][102][102];
int height, width;
pair<int,int> prisoner[2];
int change_pos[4][2] = {{1,0}, {-1,0}, {0, 1}, {0, -1}};

struct VertexInfo{
  int r;
  int c;
  int cost;

  bool operator<(const VertexInfo& x)const{
    return cost > x.cost;
  }
};

void Dijkstra(int person_idx, int start_r, int start_c){
  priority_queue<VertexInfo> pq;
  pq.push({start_r, start_c, 0});
  min_door[person_idx][start_r][start_c] = 0;

  int r,c,cost,next_r, next_c, next_cost;
  char next_state;
  while(!pq.empty()){
    r = pq.top().r;
    c = pq.top().c;
    cost = pq.top().cost;
    pq.pop();

    if(min_door[person_idx][r][c] < cost)
      continue;

    for(int i=0; i<4;++i){
      next_r = r+ change_pos[i][0];
      next_c = c+ change_pos[i][1];

      if(next_r < 0 || height+1 < next_r  || next_c < 0 || width+1 < next_c)  //범위 확인
        continue;

      next_state = prison[next_r][next_c];
      next_cost = cost;

      if(next_state == '*') //벽이라면 그냥 넘어감
        continue;
      else if(next_state == '#')  //문이라면 cost를 증가
        ++next_cost;

      if(next_cost < min_door[person_idx][next_r][next_c]){
        pq.push({next_r, next_c, next_cost});
        min_door[person_idx][next_r][next_c] = next_cost;
      }
    } //for end
  } //while end

}

int main(){
  ios_base::sync_with_stdio(0);
  int test_num;
  cin>>test_num;

  while(test_num--){
    cin>>height>>width;
    
    int order = 0;
    string st;
    for(int r= 1; r<=height ; ++r){
      cin>>st;
      st = '.' + st + '.';
      for(int c=0; c<=width+1 ; ++c){
        prison[r][c] = st[c];
        if(prison[r][c] == '$')
          prisoner[order++] = {r,c};
      }
    }

    for(int c=0; c<=width+1 ; ++c){
      prison[0][c] = '.';
      prison[height+1][c] ='.';
    }

    memset(min_door, 0x7f, sizeof(min_door));    //문제의 초기화 부분
    Dijkstra(0, 0 , 0);
    Dijkstra(1, prisoner[0].first , prisoner[0].second);
    Dijkstra(2, prisoner[1].first , prisoner[1].second);

    int min_open_num = INT32_MAX;
    int opened_doors;
    for(int r= 0; r<=height+1 ; ++r){
      for(int c=0; c<=width+1 ; ++c){
        if(prison[r][c] == '*')
          continue;

        opened_doors = min_door[0][r][c] +min_door[1][r][c] + min_door[2][r][c];
        if(prison[r][c] == '#') //해당 좌표가 문인 경우
          opened_doors -=2;
        min_open_num = min(opened_doors, min_open_num);
      }
    }

    cout<<min_open_num<<'\n';
  }
  
  return 0;
}

palilo 2년 전 1

0x3f3f3f3f 세 개를 더하면 오버플로우 나서 음수가 되고

0x7f7f7f7f 세 개를 더하면 오버플로우 나서 양수가 돼요

jin1303 2년 전 0

@palilo

답변 감사합니다 ㅠㅠ

그런데 3개의 min_door 값을 더하는 시점은 이미 다익스트라 함수로 최소로 열어야 하는 문의 수를 이미 모두 구한 시점입니다.

다익스트라 함수에서 감옥의 벽인 '*'은 접근하지 않고 건너 뛰었습니다.(50 번째줄)

따라서 감옥의 벽을 제외하고 모든 위치의 min_door값은 0x3f3f3f3f에서 최소 열어야하는 문의 수로 변경되었을 것입니다.

0x3f3f3f3f의 값이 3개가 더해지는 경우는 문의 수를 구하지 않은(다익스트라 함수의 계산에서 제외시킨) 벽을 나타내는 '*'를 계산할 때입니다.

하지만 98번째 줄에서 감옥의 벽 '*'은 continue로 계산을 건너 뛰었습니다.

그러므로 pililo님이 알려주신 오버플로우로 인한 오답이 발생하는 것은 아니지 않을까요?

palilo 2년 전 1

***

*.*

***

이런 경우 가운데 공간은 벽이 아니지만 min_door는 infinity값이겠죠

jin1303 2년 전 0

@palilo

이런 예외가 있었네요.. 감사합니다!!

저는 사실상 제대로 문제를 푼게 아니네요 ㅠㅠ

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

문제

문제

출처

ICPC

해결은 했지만 memset의 초기화 값에서 이해가 안 되는 문제가 있습니다.

jin1303 2년 전 0

palilo 2년 전 1

jin1303 2년 전 0

palilo 2년 전 1

jin1303 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말