글 읽기 - 물이 가는 길 bfs 값을 찍어봤는데 이상한 값이 나오네요.

ndkim11 3년 전 0

고슴도치가 가는 길& 물이 가는 길을 각각 bfs로 탐색하고 각 칸마다 걸린 시간을 배열에 저장했어요. 그런데

3 6
D...*.
.X.X..
....S. 예제에서 물이 가는 길이 이런 식으로 나오네요.

-132121
5-13-112
654323

2행 1열에 5가 아니라 7이 나와야 하는데 어떤 문제 때문에 5가 나오는지 몇 시간째 못 찾고 있어요ㅠㅠ.

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
//백준 3055 탈출
using namespace std;

int goseumdochi[50][50]; //time it took to reach
int water[50][50];       //time it took to reach
int row, column;

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

void goseumdochi_bfs(pair<int, int> start);
void water_bfs(pair<int, int> start);

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> row >> column;
  char map[row][column];

  pair<int, int> S;
  pair<int, int> D;
  for (int i = 0; i < row; i++)
  {
    for (int j = 0; j < column; j++) //inserting map
    {
      cin >> map[i][j];
      if (map[i][j] == 'S')
        S = make_pair(i, j);

      if (map[i][j] == 'D')
      {
        D = make_pair(i, j);
        water[i][j] = -1;
      }

      if (map[i][j] == '*') //water starting point
      {
        //water[i][j] = 0;
        water_bfs(make_pair(i, j));
        water[i][j] = 0;
      }

      if (map[i][j] == 'X') //unreachable point
      {
        goseumdochi[i][j] = -1;
        water[i][j] = -1;
      }
    }
  }
  goseumdochi_bfs(S);

  for (int i = 0; i < row; i++)
  {
    for (int j = 0; j < column; j++)
    {
      cout << goseumdochi[i][j];
    }
    cout << '\n';
  }

  for (int i = 0; i < row; i++)
  {
    for (int j = 0; j < column; j++)
    {
      cout << water[i][j];
    }
    cout << '\n';
  }

  if (goseumdochi[D.first][D.second] == 0)
    cout << "KAKTUS" << endl;
  else
    cout << goseumdochi[D.first][D.second] << endl;
}

void goseumdochi_bfs(pair<int, int> start)
{
  //cout << "goseum" << endl;
  queue<pair<int, int>> q;
  q.push(start);
  while (!q.empty()) //recording time is done
  {
    for (int i = 0; i < 4; i++)
    {
      pair<int, int> new_goseum_location(q.front().first + dy[i], q.front().second + dx[i]); //surrounding 고슴도치 blocks

      if (new_goseum_location.first >= 0 && new_goseum_location.first < row && new_goseum_location.second >= 0 && new_goseum_location.second < column) //within range
      {
        if (goseumdochi[new_goseum_location.first][new_goseum_location.second] == 0) //not visited
        {
          if (goseumdochi[q.front().first][q.front().second] + 1 < water[new_goseum_location.first][new_goseum_location.second] || water[new_goseum_location.first][new_goseum_location.second] == -1) //faster than water
          {
            goseumdochi[new_goseum_location.first][new_goseum_location.second] = goseumdochi[q.front().first][q.front().second] + 1; //recond 고슴도치 new location time
            q.push(new_goseum_location);
          }
        }
      }
    }
    q.pop();
  }
}

void water_bfs(pair<int, int> start)
{
  //cout << "water" << endl;
  queue<pair<int, int>> q;
  q.push(start);
  while (!q.empty())
  {
    for (int i = 0; i < 4; i++)
    {
      pair<int, int> new_water_location(q.front().first + dy[i], q.front().second + dx[i]);
      if (water[new_water_location.first][new_water_location.second] == -1)
        continue;
      if (new_water_location.first >= 0 && new_water_location.first < row && new_water_location.second >= 0 && new_water_location.second < column) //within range
      {
        if (water[new_water_location.first][new_water_location.second] > water[q.front().first][q.front().second] + 1 || water[new_water_location.first][new_water_location.second] == 0) //if it takes less time -> switch
        {
          water[new_water_location.first][new_water_location.second] = water[q.front().first][q.front().second] + 1; //recond 고슴도치 new location time
          q.push(new_water_location);
        }
      }
    }
    q.pop();
  }
}

paa0609 3년 전 1

42 ~ 54번 줄에서 돌의 위치를 받기 전에 water_bfs함수를 호출하네요

그래서 돌 없이 물이 흘러서 값이 예상과 다르게 나오는 것 같아요.

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

문제

문제

출처

ICPC

물이 가는 길 bfs 값을 찍어봤는데 이상한 값이 나오네요.

ndkim11 3년 전 0

paa0609 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말