글 읽기 - 92%에서 틀렸다고 나옵니다 ㅠㅠ 고수님들 도와주세요

jsstar522 3년 전 0

게시판에 있는 모든 반례, 예제, 구글링으로 찾을 수 있는 반례를 다 넣어봐도 어디가 잘못되었는지 모르겠습니다.

활성 바이러스가 퍼지면서 비활성 바이러스를 자연스럽게 통과하는 것도 구현했구요.

문제는 잘 이해한것같은데 제가 놓치는게 있을까요..?

정답은 dfs로 지정한 바이러스 위치로부터 counter[][] 배열에 1초씩 더해가며 퍼져가도록 구현했으며, 여기에서 최대값을 구하는 방식입니다.

예를들어 (0,0)에 바이러스가 4x4 배열에서 바이러스가 퍼져나간다면 다음과 같이 counter 배열이 만들어집니다.

0 1 2 3

1 2 3 4

2 3 4 5

3 4 5 6

이렇게 되면 최대값은 6이므로 6초가 정답이 됩니다. 중간에 벽이나 비활성기체가 있는 예시도 들어드리겠습니다.

4 1

2 0 0 0

0 0 0 0

1 2 1 1

0 0 0 0

이런식으로 input을 넣으면 counter 배열은

0 1 2 3
1 2 3 4
0 -1 0 0
5 4 5 6

와

-1 2 3 4
2 1 2 3
0 0 0 0
2 1 2 3

이렇게 두가지 경우의 수가 나오게 되며, 최소값인 4가 답이됩니다.

설명이 좀 길었네요 ㅠㅠ 도와주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, M;
int map[50][50];        // default
int new_map[50][50];    // 활성바이러스 체크 한뒤의 map

int counter[50][50];        // 각 칸까지 퍼지는데 걸리는 시간
int visited[50][50];        // bfs visited
int dfs_visited[50][50];    // dfs visited

queue <pair <int, int> > virus_pos;
queue <int> virus_count;

int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};   //상하좌우

int isExist = 0;        // 빈칸의 존재여부
int result = 50*50+1;   // 바이러스 퍼지는 시간 최대값

int init_visited(){
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      visited[i][j] = 0;
    }
  }

  return 0;
}

int check(){
  int temp = 0;
  
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      if(temp < counter[i][j]) temp = counter[i][j];    // counter가 가장 큰 값이 총 걸린 시간이다
      if(map[i][j] == 0 && visited[i][j] == 0){         // map , visited 배열 검사했을 때 둘다 0인 자리는 빈칸인데 확인을 못하는 곳이므로 도달하지 못하는 공간
        return -1;
      }
    }
  }
  return temp;
}

int bfs(){
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      if(new_map[i][j] == 2){
        virus_pos.push(make_pair(i, j));
        virus_count.push(0);
      }
    }
  }
  while(!virus_pos.empty()){
    int now_y = virus_pos.front().first;
    int now_x = virus_pos.front().second;
    int now_count = virus_count.front();
    
    counter[now_y][now_x] = now_count;
    if(new_map[now_y][now_x] == -1){    // 비활성 바이러스
      counter[now_y][now_x] = -1; // 표시만 -1로 해놓자 (나중에 counter 배열에서 최대값이 걸린 총 시간이 되는데, 최대값이 비활성 바이러스 위치일 수 있으므로)
    }
    visited[now_y][now_x] = 1;
    virus_pos.pop();
    virus_count.pop();

    for(int i=0; i<4; i++){
      if(now_y + dir[i][0] >= 0 && now_y + dir[i][0] < N && now_x + dir[i][1] >= 0 && now_x + dir[i][1] < N && visited[now_y+dir[i][0]][now_x+dir[i][1]] != 1 && new_map[now_y+dir[i][0]][now_x+dir[i][1]] != 1){
        visited[now_y+dir[i][0]][now_x+dir[i][1]] = 1;
        virus_pos.push(make_pair(now_y + dir[i][0], now_x + dir[i][1]));
        virus_count.push(now_count + 1);
      }
    }
  }

  // 바이러스가 퍼지는데 걸리는 시간 카운트한 배열
  // cout << "-----------------" << endl;
  // for(int i=0; i<N; i++){
  //   for(int j=0; j<N; j++){
  //     cout << counter[i][j] << " ";
  //   }
  //   cout << endl;
  // }

  return 0;
}

int dfs(int count, int dy, int dx){
  if(count == M){
    init_visited();
    // 선택된 바이러스만 2로 두고, 나머지 2는 -1으로 둔다.
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
        if(map[i][j] == 2 && dfs_visited[i][j] != 1){   // 선택되지 않은 바이러스일 경우(비활성 바이러스) -1으로 처리
          new_map[i][j] = -1;
        }
        else{
          new_map[i][j] = map[i][j];
        }
      }
    }

    bfs();

    // -1이 하나라도 아닌 경우의 수가 있다면 -1은 답이 될 수 없다
    if(check() != -1){
      isExist = 1;
      if(result > check()) result = check();
    }

    return 0;
  }

  while(1){
		if(map[dy][dx] == 2 && dfs_visited[dy][dx] != 1){
			dfs_visited[dy][dx] = 1;
			dfs(count + 1, dy, dx);
			dfs_visited[dy][dx] = 0;
		}
		if (dx == N-1 && dy == N-1) break;
		if(dx == N - 1){
			dy++;
			dx = 0;
		}else{
			dx++;
		}
	}

  return 0;
}


int main(){
  // 5C2로 조합을 고른다
  // 고르고 나면 나머지 비활성기체는 그냥 빈칸으로 만든다
  // queue를 이용해서 바이러스를 퍼뜨린다

  // 1개의 경우의 수 끝나면 빈칸있는지 조사하고 result를 counter로 저장
  // 빈칸이 있으면 -1로 저장
  // 가장 작은 값 출력

  cin >> N >> M;
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      cin >> map[i][j];
    }
  }

  dfs(0, 0, 0);

  if(isExist){
    cout << result << endl;
  }
  else{
    cout << -1 << endl;
  }

  return 0;
}

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

문제

문제

출처

ICPC

92%에서 틀렸다고 나옵니다 ㅠㅠ 고수님들 도와주세요

jsstar522 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말