[백준] 2615번 오목 (C)

출처

한국정보올림피아드 KOI 2003 초등부 1번

문제 번호

코드업 : 4023 : 오목
백준 : 2615 오목

알고리즘

DFS

풀이

기존의 DFS 방식에서 방향에 대한 정보만 추가하면 된다. 승자와 가장 왼쪽 바둑돌의 위치를 출력하는 것이 목적이기 때문에 DFS를 시작한 바둑돌이 가장 왼쪽 위에 있도록 해줘야 한다. 따라서 아래 표의 순서대로 탐색을 해준다.

1	4	7
2	5	8
3	6	9

 

이제 방향 배열을 잡아줘야 하는데 현재 원소의 왼쪽에 있는 데이터들과 왼쪽 위에 있는 데이터들은 이미 확인했으므로 확인할 필요가 없다. 시작한 바둑돌이 가장 왼쪽 위에 있도록 탐색하려고 하기 때문에 오른쪽에 있는 바둑돌들만 확인해 주면 된다.

 

이미 확인	이미 확인	이제 볼거
이미 확인	*	이제 볼거
이미 확인	이제 볼거	이제 볼거

 

check 배열을 위치와 방향을 담을 수 있도록 19*19*4로 잡아준다. 이렇게 하면 연속된 바둑돌이 5개 초과인 경우도 고려해 줄 수 있다.
1 1 1 1 1 1 인 경우(6개) 두번째 1에서 부터 시작하면 5개로 세어지는것을 막아준다.

 

#include<iostream>
using namespace std;

int dir[8][2]={{1,0},{0,1},{1,1},{-1,1}};
int in[20][20];
int check[20][20][4];

int dfs(int a, int b, int d){

    int cnt=1;
    check[a][b][d]=1;
    int na=a+dir[d][0],nb=b+dir[d][1];

    if(in[a][b]==in[na][nb])
        cnt+=dfs(na,nb,d);

    return cnt;
}

int main(){
    int flag=1;
    for(int i=1;i<=19;i++){
        for(int j=1;j<=19;j++){
            cin>>in[i][j];
        }
    }    
    //cout<<"hi";

    for(int i=1;i<=19;i++){
        for(int j=1;j<=19;j++){
            if(in[j][i]==0)
                continue;
            for(int k=0;k<4;k++){
                if(check[j][i][k])
                    continue;
                if(dfs(j,i,k)==5)
                {
                    cout<<in[j][i]<<"\n"<<j<<" "<<i;
                    flag=0;
                }        
            }
        }
    }
    if(flag){
        cout<<0;
    }    
}

 

결과