[BOJ / C++] #2615 오목

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

문제 풀이

오목 판의 모든 칸에서 시작해서 모든 방향으로 5개의 오목이 놓아져있는지 탐색을 진행하면 되는데 이때
방향은

➡️↘️⬇️↗️ 이렇게 4가지만 진행하면 된다. (어차피 모두 같은 방향축이기 때문)

여기서 중요한 것은 6개 이상 놓인 것은 이긴 경우가 아니므로, 각 방향을 탐색하기 전 바로 그 방향의 전 오목이 놓였는지 안 놓였는지 확인하여야 한다. (즉, 현재 오목이 탐색하려는 방향의 시작 오목인지 확인!)

탐색은 총 4가지 방향으로
search1, search2, search3, search4 함수로 구현하였다.
오목판 범위가 넘어가지 않을 때까지 해당 방향으로 연속된 오목의 개수를 세서 5개가 되면 참을 리턴한다.

✨검은색 또는 흰색이 이겼을 경우에는 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알의 가로줄 번호와 세로줄 번호(세로로 놓인 경우, 그 중 가장 위에 있는 것)를 출력해야 하므로 시작점이 가장 왼쪽에 있는 ➡️↘️⬇️↗️ 방향으로 search 함수를 호출하도록 만들었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 30
int map[MAX][MAX];
bool visited[MAX][MAX];

// ➡️↘️⬇️↗️
int dr[4]={0,1,1,-1};
int dc[4]={1,1,0,1};

// ➡️ ️
bool search1(int color, int r, int c, int cnt){
    while(true){
        if(c+1>19) break;
        if(map[r][++c]==color) cnt++;
        else break;
    }
   return cnt == 5;
}

// ↘️ ️
bool search2(int color, int r, int c, int cnt){
    while(true){
        if(c+1>19||r+1>19) break;
        if(map[++r][++c]==color) cnt++;
        else break;
    }
    return cnt == 5;
}

//  ⬇️
bool search3(int color, int r, int c, int cnt){
    while(true){
        if(r+1>19) break;
        if(map[++r][c]==color) cnt++;
        else break;
    }
    return cnt == 5;
}

// ↗️
bool search4(int color, int r, int c, int cnt){
    while(true){
        if(c+1>19||r-1<1) break;
        if(map[--r][++c]==color) cnt++;
        else break;
    }
    return cnt == 5;
}


int main(){
    for(int i=1;i<=19;i++){
        for(int j=1;j<=19;j++){
            cin>>map[i][j];
        }
    }

    for(int i=1;i<=19;i++){
        for(int j=1;j<=19;j++){
            if(!map[i][j]) continue;

            //1. ➡️
            if(map[i][j-1]!=map[i][j]&&search1(map[i][j],i,j,1)){
                cout<<map[i][j]<<"\n"<<i<<" "<<j<<"\n";
                return 0;
            }

            //2. ↘️
            if(map[i-1][j-1]!=map[i][j]&&search2(map[i][j],i,j,1)){
                cout<<map[i][j]<<"\n"<<i<<" "<<j<<"\n";
                return 0;
            }

            //3. ⬇️
            if(map[i-1][j]!=map[i][j]&&search3(map[i][j],i,j,1)){
                cout<<map[i][j]<<"\n"<<i<<" "<<j<<"\n";
                return 0;
            }

            //4. ↗️
            if(map[i+1][j-1]!=map[i][j]&&search4(map[i][j],i,j,1)){
                cout<<map[i][j]<<"\n"<<i<<" "<<j<<"\n";
                return 0;
            }
        }
    }

    cout<<0<<"\n";
    return 0;
}