[백준 2615] 오목

[백준 2615] 오목

문제 링크

#include "header.h"
using namespace std;
int board[24][24];
int visit[24][24][10];
int dx[4] = {1, 0, 1, 1};
int dy[4] = {0, 1, -1, 1};
queue <pair<int, int>> q;
void input() {
  for(int i=0; i<19; i++){
    for(int j=0; j<19; j++) {
      cin >> board[i][j];
      if(board[i][j]) q.push({i, j});
    }
  }
}
bool cmp(pair<int, int>&a, pair<int, int>&b) {
  return a.second < b.second;
}
void solve() {

  while (!q.empty()){
    vector <pair<int, int>> candidate;
    int target_x = q.front().first;
    int target_y = q.front().second;
    int target = board[target_x][target_y];
    q.pop();
    candidate.push_back({target_x, target_y});

    // 방향
    for(int i=0; i<4; i++) {
      visit[target_x][target_y][i] = 1;
      int nx = target_x + dx[i];
      int ny = target_y + dy[i];    
      if(visit[nx][ny][i] || board[nx][ny] != target || nx < 0 || ny < 0 || nx >= 19 || ny >= 19) continue;
      int cnt = 0;
      
      while (1){
        nx += dx[i];
        ny += dy[i];
        if(visit[nx][ny][i] || board[nx][ny] != target || nx < 0 || ny < 0 || nx >= 19 || ny >= 19) break;
        candidate.push_back({nx, ny});
        visit[nx][ny][i] = 1;
        cnt++;
      }

      if(cnt == 3) {
        sort(candidate.begin(), candidate.end(), cmp);
        cout << target << endl;
        cout << candidate[0].first + 1 << ' ' << candidate[0].second + 1<< endl;
        return;
      }
      
    }
  }
  cout << 0 << endl;

}
int main() {
  input();
  solve();
  return 0;
}

• 시뮬레이션 문제, 오목을 판별하는 문제이다.
• 대신, 6목이 되면 안된다!
• 반복문을 돌면서, 0이 아닌 것들을 다 큐에 넣고 하나씩 빼면서 오목인지 판별 해 주면 된다.
• 8방향을 모두 탐색 할 필요가 없기 때문에 (가장 빠른 돌부터 탐색 하기 때문에) 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래만 탐색 해 준다.
• 방향이 같다면, 해당 방향으로 쭉 탐색을 해 준다.
• cnt가 3(총 돌의 갯수가 5개)이라면 6목인지 확인 해 준다.
• candidate라는 벡터 안에, 해당 오목의 돌들을 넣어주었기 때문에, y좌표가 제일 빠른 좌표를 출력 해 준다.