BOJ 2615 - 오목(C++)

 

https://www.acmicpc.net/problem/2615

2615번: 오목

 

풀이

자표와 방향성에 대해 탐색했는지 확인을 위한 bool 3차원 배열 visit 사용

오목판의 현재 위치에 대해 8방향을 탐색해야하지만 2중 for문을 이용해 왼쪽에서 오른쪽, 위에서 아래로 탐색하기 때문에 4방향으로만(동, 남동, 남, 남서) 제한하여 탐색

 

위의 방향으로 탐색할 경우 (1, 1)을 시작으로 연속되었는지 확인 한 후 (2, 2)에서 (1, 1)로 연속성을 확인

비효율적이고 visit을 이용하여 확인하기 어려움

* 이러한 방식으로 사용하기 위해서는 2차원 배열을 아래에서 위로, 오른쪽에서 왼쪽으로 탐색해야함

 

 

∴ 일반적인 탐색 방향에 맞춰 위의 방향성을 이용

ex) (1, 1) -> (2, 2)로 연속성을 확인, visit에 저장 다음 탐색 위치인 (2, 2)에서는 좌표, 방향성에 대해 visit에 방문 여부가 저장되었기 때문에(2, 2) 좌표에서 남동쪽으로(이전 탐색과 같은 결과기 때문에) 탐색할 필요 없음

 

 

1. 2중 for문으로 오목판 배열에 1 or 2가 있다면 2로 넘어감 

2. 1의 좌표에서 4방향에 대한 다음 좌표값을 확인, 같은 값이라면 1의 좌표를 vector에 저장하고 3으로 

3. 2의 좌표와 방향성을 확인하며 연속되는 좌표까지 반복하며 vector에 저장, 연속되지 않는 다면 4로

4. 3에서 확인된 연속되는 좌표의 수가 5라면 연속된 값과 2~3까지 저장한 vector를 정렬한 값의 0번째 요소를 출력하고 return

  * 정렬 조건 -> 1. 열값이 작은순 2. 열값이 같다면 행값이 작은순

5. 3에서 확인된 연속되는 좌표의 수가 5가 아니라면, 2로 돌아가서 다음 방향성에 대해 조사, 해당 좌표에 대한 탐색이 끝나면 1로 돌아가서 다음 시작점에 대해 조사 

1의 모든 시작점에 대해 4의 결과가 나오지 않는다면 우승한 돌이 없기 때문에 0을 출력

 

* 다른 3방향의 경우 정렬조건에 맞게 탐색 되어 vector와 정렬을 사용 할 필요 없지만, 남서 방향 탐색은 정렬조건과 다르기 때문에 vector와 정렬을 사용

* 풀고난 후 풀이와 같이 탐색 횟수를 최소화하면서 vector나 정렬을 필요 없을 경우에 대해 고민하고 찾아봐도 없었음......

 

 

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

using namespace std;

int N=19;
int map[20][20];
bool visit[20][20][4];
int dy[] = { 0, 1, 1, 1 };
int dx[] = { 1, 1, 0, -1 };
vector<pair<int, int>> pos;

// vector에 넣은 좌료를 정렬 1. 열 값이 작은 것 2. 열값이 같을 시에 행 값이 작은 순
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second >= b.second)
        if (a.second == b.second)
            if (a.first > b.first)
                return false;
            else
                return true;
        else
            return false;
    else
        return true;
}

// 현재 좌표에 대해 박스 밖으로 나가는 확인
bool isrange(int y, int x) {
    if (y<1 || x<1 || y>N || x>N) return false;
    return true;
}

// dfs 현재 자표에서 연속되는 방향에 대해 탐색, 연속되는 갯수를 반환
int check_next(int now_y, int now_x, int dir, int val, int cnt) {
    visit[now_y][now_x][dir] = true;
    pos.push_back(make_pair(now_y, now_x));
    
    int next_y = now_y + dy[dir];
    int next_x = now_x + dx[dir];
    // 시작점에 대해 방향성에 대해 탐색 했기 때문에 
    // 해당 함수에서 연속되는 탐색에 대해서는 visit을 확인할 필요 없음, 어차피 false
    if (!isrange(next_y, next_x) || map[next_y][next_x] != val) return cnt;

    return check_next(next_y, next_x, dir, val, cnt + 1);
}

int main() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (map[i][j] == 0)continue;
            // 시작점에 대해 4방향 확인
            // 같은 값에 대해 연속성을 가지면 dfs 탐색
            for (int d = 0; d < 4; d++) {
                int ny = i + dy[d];
                int nx = j + dx[d];

                if (!isrange(ny, nx))continue;
                if (map[ny][nx] == map[i][j] && !visit[i][j][d]) {
                    pos.clear();
                    visit[i][j][d] = true;
                    pos.push_back(make_pair(i, j));
                    if (check_next(ny, nx, d, map[i][j], 2) == 5) {
                        sort(pos.begin(), pos.end(), cmp);
                        cout << map[i][j] << endl;
                        cout << pos[0].first << ' ' << pos[0].second;
                        return 0;
                    }
                }
            }
        }
    }
    // 위의 for문에서 return 되지 않는 다면 이긴 돌이 없다는 의미
    cout << 0;
    return 0;
}