글 읽기 - 반례 찾아주실 수 있을까요?

shadowpur97 3년 전 0

안녕하세요! 요즘 심심풀이로 백준 문제 깨기 중인 사람입니다.

다름이 아니라 코드 제출시에 틀렸다고 나오는데, 여러 케이스를 다 넣어봐도 도저히 찾기가 어려워서요 ㅠㅠ

혹시 어디가 틀렸다던지, 반례라던지 도움을 주실 분 있을까요??

간단하게 코드를 설명 드리자면,

tomat 배열은 M*N*H 행렬로 입력 받은 토마토의 상태를 저장합니다! 익은 곳은 1으로, 안 익은 곳은 0, 빈 칸은 -1로 저장합니다!

visit 배열도 M*N*H 행렬로 bfs 순회시에, 이 칸이 방문한 칸인지 확인하는 용도 겸 최단 거리 저장하는 용도로도 쓰입니다!

그래서, tomat 배열의 모든 칸에 입력이 끝나면,

1. 익은 토마토가 저장된 위치의 visit 값을 1로 만들고, 큐에 넣습니다.

2. 큐에서 하나를 끄집어냅니다.

3. 다음 6방향 칸 중에 visit값이 0인 칸에는 visit[현재 위치] + 1을 저장하고 큐에 그 칸을 넣습니다.

4. 1~3 과정을 큐가 빌 때까지 반복

요렇게 되면 익을 수 있는 토마토가 저장된 칸은 큐에 "최단거리-1"이 저장될 거고,

익지 못하는 토마토가 저장된 칸이나 애초에 빈 칸은 0이 저장됩니다.

요렇게 풀었습니다!

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

typedef pair<int, int> xy;
typedef pair<xy, int> xyz;

int main(){
  int M, N, H;
  cin >> M >> N >> H;

  int tomat[M][N][H];
  int visit[M][N][N];

  bool all_ripen = true;

  queue<xyz> ripen;

  memset(visit, 0, sizeof(visit));

  for(int kdx = 0; kdx < H; kdx++)
  {
    for(int jdx = 0; jdx < N; jdx++)
    {
      for(int idx = 0; idx < M; idx++)
      {
        cin >> tomat[idx][jdx][kdx];

        int tmp = tomat[idx][jdx][kdx];
        if(tmp == 0)
          all_ripen = false;
        if(tmp == 1)
        {
          ripen.push({{idx, jdx}, kdx});
          visit[idx][jdx][kdx] = 1;
        }
      }
    }
  }

  while(!ripen.empty())
  {
    int x = ripen.front().first.first;
    int y = ripen.front().first.second;
    int z = ripen.front().second;

    ripen.pop();

    int move_x[6] = {0, 0, 0, 0, -1, 1};
    int move_y[6] = {0, 0, 1, -1, 0, 0};
    int move_z[6] = {1, -1, 0, 0, 0, 0};

    for(int idx = 0; idx < 6; idx++)
    {
      int next_x = x + move_x[idx];
      int next_y = y + move_y[idx];
      int next_z = z + move_z[idx];

      if(next_x == M || next_x == -1)
        continue;

      if(next_y == N || next_y == -1)
        continue;

      if(next_z == H || next_z == -1)
        continue;

      if(tomat[next_x][next_y][next_z] == 0 && visit[next_x][next_y][next_z] == 0)
      {
        ripen.push({{next_x, next_y}, next_z});
        visit[next_x][next_y][next_z] = visit[x][y][z] + 1;
      }
    }
  }

  if(all_ripen){
    cout << 0;
    return 0;
  }

  int max = 0;

  for(int idx = 0; idx < M; idx++)
  {
    for(int jdx = 0; jdx < N; jdx++)
    {
      for(int kdx = 0; kdx < H; kdx++)
      {

        int tmp = visit[idx][jdx][kdx];
        if(tomat[idx][jdx][kdx] != -1 && tmp == 0)
        {
          cout << -1;
          return 0;
        }
        if(tomat[idx][jdx][kdx] != -1 && tmp > max)
          max = tmp;
      }
    }
  }
  cout << max-1 << '\n';

  /*
  for(int kdx = 0; kdx < H; kdx++)
  {
    for(int jdx = 0; jdx < N; jdx++)
    {
      for(int idx = 0; idx < M; idx++)
        cout << visit[idx][jdx][kdx];
      cout << "\n";
    }
    cout << '\n';
  }
  */
}
    

rnjstpgns91 3년 전 1

잘 하셨는데 14번째 줄에 실수가 있으셨네요. 고치시면 통과 됩니다!

shadowpur97 3년 전 0

ㅗㅜㅑ 당신은 천재에요 감사드립니다ㅠㅠㅠㅠㅠ

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