글 읽기 - c++ 질문에 있는 반례 확인해보았는데도 틀렸다고 나오네요.. ㅠ

wltjdals422 3년 전 1

안녕하세요, 배추벌레 잡는 문제 풀다가 의문이 생겨서 질문드립니다.

저는 일단 dfs 방식으로 상하좌우에 있는 요소들을 검사하여 모두 체크하고 나면 answer+1 해주는 방식으로 구현해봤습니다.

테스트 케이스에 있는 예제 모두 잘 되고, 질문 게시판들에 있는 반례들도 모두 대입해봤는데 결과가 잘 나왔었습니다. 그런데 "틀렸습니다"가 나오네요..

그리고 질문에 초기화에 대한 것이 많던데, 저는 일단 dfs 체크하고 나면 1 -> 0으로 모두 바꿔주기 때문에 초기화할 필요가 없다고 생각하지만 혹시 몰라 memset으로 초기화를 해주었습니다.

지금 상태에서는 무엇이 잘못되었는지 모르겠는데, 혹시 반례 알려주신다면 감사하겠습니다...!!

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;
int arr[50][50];
int N, _N, x, y, cntx, cnty, answer=0;

void dfs(int _x, int _y) {
  arr[_x][_y] = 0;
  int left = _x-1, right = _x+1, top = _y-1, bottom = _y+1;
  if(0<= left < cntx) {
    if(arr[left][_y] == 1) dfs(left, _y);
  }
  if(0 <= right < cntx) {
    if(arr[right][_y] == 1) dfs(right, _y);
  }
  if(0 <= bottom < cnty) {
    if(arr[_x][bottom] == 1) dfs(_x, bottom);
  }
  if(0 <= top < cnty) {
    if(arr[_x][top] == 1) dfs(_x, top);
  }
}

int main(void) {
  cin >> N;
  vector<int> result(N,0);

  for(int i=0; i<N; i++) {
    answer=0;
    cin >> cntx >> cnty >> _N;
    for(int j=0; j<_N; j++) {
      cin >> x >> y;
      arr[x][y] = 1;
    }
    for(int _x=0; _x<cntx; _x++) {
      for(int _y=0; _y<cnty; _y++) {
        if(arr[_x][_y] == 0) continue;
        else {
          dfs(_x, _y);
          answer++;
        }
      }
    }
    result[i] = answer;
    memset(arr, 0, sizeof(arr));
  }

  for(int i=0; i<result.size(); i++) {
    cout << result[i] << endl;
  }
}

mokiia 3년 전 1

0 <= left < cntx 이 부분이 문제입니다.

c++ 연산자 우선순위에 따르면 저 식은 (0 <= left) < cntx가 되는데 우선 0 <= left의 값을 계산하면 식이 참일땐 1, 거짓일땐 0입니다.

그러면 최초의 식은 0 <= left가 참일때는 1 < cntx, 거짓일때는 0 < cntx가 되어 의도하신 것과는 다르게 동작하게 됩니다.

wltjdals422 3년 전 0

아... 맞네요 저 당연히 && 연산자 사용했다고 생각했는데.. 왜그랬지... ㅠㅠ

너무 당연한 질문 성심성의껏 답변해주셔서 감사합니다!!

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

문제

문제

출처

ICPC

c++ 질문에 있는 반례 확인해보았는데도 틀렸다고 나오네요.. ㅠ

wltjdals422 3년 전 1

mokiia 3년 전 1

wltjdals422 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말