글 읽기 - C++ 오목 문제 반례 요청합니다. (6목, 가장 왼쪽 돌 조건 통과)

andyaaa78 1년 전 0

안녕하세요.

오목 문제 반례를 요청하고자 질문글 올립니다.

글 읽기 - 누가 기침소리를 내었는가? (acmicpc.net)

글 읽기 - 오목 문제 반례 찾습니다! (acmicpc.net)

등 백준 질문글에 존재하는 대부분의 테스트 케이스로 테스트해 보았으나 반례를 발견하지 못했습니다.

6목인 경우 처리, 그리고 아래와 같이 가장 왼쪽(세로라면 위쪽) 돌을 찾는 경우도 처리했습니다.

ㅇ ㅇ ㅇ

ㅇ ㅁ ㅅ

ㅅ ㅅ ㅅ

ㅁ을 탐색하고 있을 때, ㅅ으로 표시된 4방향으로 진행하고, 다음 진행 방향의 좌표를 ans_case 배열에 저장한 후 sort하여 가장 왼쪽에 있는(세로의 경우 가장 위) 돌을 찾아내도록 구현했습니다.

제가 어느 부분을 빠뜨렸는지 깨우쳐 주시면 감사드리겠습니다.

좋은 하루 보내세요!

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

using namespace std;

int arr[21][21] = {0};
int R_cor[4] = {0, 1, 1, 1};
int C_cor[4] = {1, 1, 0, -1};
//바둑알이 있는 경우를 모두 담는 벡터
vector<pair<int, int>> v;
int currCnt;
//계속 갱신되는 ans_case : 정답인 순간에 출력
pair<int, int> ans_case[6];
int exit_code = 0;

bool compare(pair<int, int> a, pair<int, int> b) {
  if (a.second != b.second)
    return a.second < b.second;
  else
    return a.first < b.first;
}

int dfs(int row, int col, int direction) {
  //같은 방향에서 앞에 돌 있는 경우 pass(이미 셌을거임)
  int prevR = row - R_cor[direction];
  int prevC = col - C_cor[direction];
  if (currCnt == 0) {
    if (prevR >= 0 && prevR <= 18 && prevC >= 0 && prevC <= 18) {
      if (arr[prevR][prevC] == arr[row][col]) return 0;
    }
  }

  int nextR = row + R_cor[direction];
  int nextC = col + C_cor[direction];
  if (nextR < 0 || nextR > 18 || nextC < 0 || nextC > 18 || currCnt > 5)
    return 0;

  if (currCnt == 4) {
    //딱 5개인 경우
    if (arr[nextR][nextC] != arr[row][col]) {
      ans_case[currCnt++] = make_pair(row, col);
      sort(ans_case, ans_case + 5, compare);
      cout << arr[row][col] << '\n'
           << ans_case[0].first + 1 << ' ' << ans_case[0].second + 1 << '\n';
      exit_code = 1;
      return 0;
    } else
      return 0;
  }
  //내용 같은 경우 같은 방향으로 재귀 호출
  if (arr[nextR][nextC] == arr[row][col]) {
    ans_case[currCnt++] = make_pair(row, col);
    dfs(nextR, nextC, direction);
    return 0;
  } else
    return 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  for (int i = 0; i < 19; i++) {
    for (int j = 0; j < 19; j++) {
      int n;
      cin >> n;
      arr[i][j] = n;
      if (n) v.push_back(make_pair(i, j));
    }
  }

  for (int i = 0; i < v.size(); i++) {
    for (int t = 0; t < 4; t++) {
      currCnt = 0;
      dfs(v[i].first, v[i].second, t);
      if (exit_code) break;
    }
    if (exit_code) break;
  }
  if (!exit_code) cout << 0 << '\n';
  return 0;
}

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

문제

문제

출처

ICPC

C++ 오목 문제 반례 요청합니다. (6목, 가장 왼쪽 돌 조건 통과)

andyaaa78 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말