백준 2615번 오목 (C++)

문제 링크 : www.acmicpc.net/problem/2615

2615번: 오목

이 문제는 실버3지만 정답률이 21.434%이며, 어지간한 골드 상위권 레벨보다도 정답률이 낮다.

그도 그럴게 문제를 대충 읽었다가는 무조건 틀릴 수 밖에 없는 구조이기 때문이다.

 

문제에서 유의사항은 다음과 같다. 여기서 특히나 1번과 4번이 중요하다.

1. 5목이 아닌 6목일 경우 이긴게 아니다.

2. 동시에 흑과 백이 이기는 판은 나오지 않는다.

3. 흑이 여러곳에서 이기거나, 백이 여러곳에서 이기는 판은 나오지 않는다.

4. 가로줄의 경우 정답 위치는 맨 왼쪽에 위치한 칸이 출력되며,

세로줄의 경우 정답 위치는 맨 위쪽에 위치한 칸이 출력되며,

대각선의 경우 정답 위치는 맨 왼쪽에 위치한 칸이 출력된다.

5. 이 문제는 Brute Force지, DFS가 아니다.

 

문제 해설은 다음과 같다.

1. 편의상 좌표는 1,1부터 19,19까지 입력받는다.

2. 2중 for문을 돌려서 1,1부터 오목의 승리 여부를 체크한다. 이때 승리 여부 체크를 위해 함수에 넘겨받는 인자들은 다음과 같다.

void bf(int y, int x, int st_y, int st_x, int num, int dir)
        // 현재 좌표 // 시작 좌표 // 여탯껏 누적된 갯수 // 움직이는 방향

3. 먼저 5목을 체크하기 위해 움직일 수 있는 방향은 다음과 같다.

 

 

Brute Force인 관계로 8방위 중에서 4방위만 선택하면 된다.

또한, 어떠한 답이 나와도 결국 대각선은 맨 왼쪽의 위치가, 세로는 맨 위쪽의 위치가, 가로는 맨 왼쪽의 위치가  최초의 위치로 선택되기 때문에 위의 이미지의 방향표를 채택해야한다.

물론 다른 방향을 선택해서 답을 출력할 수 있지만, 식이 조금 번거로운 부분이 발생할 수 있다.

또한 왜 위쪽이 -1, 1로 가는거지? +1, 1이 아닌가? 라는 생각이 든다면... 0, 0부터 시작된다는 점을 다시 한번 떠올려보자.

 

4. 다음은 코드를 보며 이해하자.

void bf(int y, int x, int st_y, int st_x, int num, int dir){
    ch[y][x] = true;
    for(int i=0; i<4; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(ny>=1&&ny<=19&&nx>=1&&nx<=19&&!ch[ny][nx]&&arr[y][x]==arr[ny][nx]){
            if(y==ny){ // 가로
                if(dir==1) bf(ny,nx,st_y,st_x,num+1,dir);
                else bf(ny,nx,y,x,2,1);
            }
            else if(x==nx){ // 세로
                if(dir==2) bf(ny,nx,st_y,st_x,num+1,dir);
                else bf(ny,nx,y,x,2,2);
            }
            else if(y-ny==1&&nx-x==1){ // 위 대각선
                if(dir==3) bf(ny,nx,st_y,st_x,num+1,dir);
                else bf(ny,nx,y,x,2,3);
            }
            else{ //아래 대각선
                if(dir==4) bf(ny,nx,st_y,st_x,num+1,dir);
                else bf(ny,nx,y,x,2,4);
            }
        }
    }
    ch[y][x] = false;
    if(num==5){
        if(dir==1){
            if((x>5&&arr[y][x]==arr[y][x-5])||(x<19&&arr[y][x]==arr[y][x+1])) return;
        }
        else if(dir==2){
            if((y>5&&arr[y][x]==arr[y-5][x])||(y<19&&arr[y][x]==arr[y+1][x])) return;
        }
        else if(dir==3){
            if((y<15&&x>5&&arr[y][x]==arr[y+5][x-5])||(y>1&&x<19&&arr[y][x]==arr[y-1][x+1])) return;
        }
        else if(dir==4){
            if((y>5&&x>5&&arr[y][x]==arr[y-5][x-5])||(y<19&&x<19&&arr[y][x]==arr[y+1][x+1])) return;
        }
        cout << arr[y][x] << "\n" << st_y << " " << st_x << "\n";
        exit(0);
    }
}

위쪽 for문을 보면, 방향이 다를 경우 갯수를 2로 초기화 시켜줘서 새로 진행하게 된다.

방향이 같을 경우 계속 같은 방향으로 왔다는 의미이므로, num+1로 갯수를 진행시키면 된다.

 

마지막으로 아래 num==5인 경우가 중요한데, 예시로 dir==1인 경우, 즉, 위 대각선인 경우를 설명해보겠다.

 

 

6,6부터 시작해서 착실히 갯수를 쌓여 1,1까지 갔다고 가정해보자.

문제에서 6개는 정답이 될 수 없으므로, num==5를 충족시키지 못하니 ch[1][1] = false로 변하고 return이 될 것이다.

문제는 그 다음이다. return이되어 2,2로 가게 되었을때, 별다른 조건을 명시하지 않으면 정답이라고 출력해버리는 불상사를 겪을 수 있다. 

때문에 위 대각선일 경우, 해당 위치의 다음 칸, 즉 arr[y-1][x+1]이 같은 값을 가지거나, 반대로 방향을 비틀어 arr[y-5][x-5]가 같은 값을 가질 경우, 해당 답은 실상은 5목을 초과한 6목, 또는 그 이상이 될 수 있음을 뜻한다.

 

반대로 모든 조건에 해당되지 않으면, 그 코드는 옳바른 5목을 뜻하므로 곧 바로 정답을 출력하고 종료하면 된다.

 

#include <iostream>
#define MAX 21
using namespace std;

bool ch[MAX][MAX] = {false,};
int arr[MAX][MAX], ny, nx, my[]={-1,0,1,1}, mx[]={1,1,1,0};

void bf(int y, int x, int st_y, int st_x, int num, int dir){
    ch[y][x] = true;
    for(int i=0; i<4; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(ny>=1&&ny<=19&&nx>=1&&nx<=19&&!ch[ny][nx]&&arr[y][x]==arr[ny][nx]){
            if(y==ny){ // 가로
                if(dir==1) bf(ny,nx,st_y,st_x,num+1,dir);
                else bf(ny,nx,y,x,2,1);
            }
            else if(x==nx){ // 세로
                if(dir==2) bf(ny,nx,st_y,st_x,num+1,dir);
                else bf(ny,nx,y,x,2,2);
            }
            else if(y-ny==1&&nx-x==1){ // 위 대각선
                if(dir==3) bf(ny,nx,st_y,st_x,num+1,dir);
                else bf(ny,nx,y,x,2,3);
            }
            else{ //아래 대각선
                if(dir==4) bf(ny,nx,st_y,st_x,num+1,dir);
                else bf(ny,nx,y,x,2,4);
            }
        }
    }
    ch[y][x] = false;
    if(num==5){
        if(dir==1){
            if((x>5&&arr[y][x]==arr[y][x-5])||(x<19&&arr[y][x]==arr[y][x+1])) return;
        }
        else if(dir==2){
            if((y>5&&arr[y][x]==arr[y-5][x])||(y<19&&arr[y][x]==arr[y+1][x])) return;
        }
        else if(dir==3){
            if((y<15&&x>5&&arr[y][x]==arr[y+5][x-5])||(y>1&&x<19&&arr[y][x]==arr[y-1][x+1])) return;
        }
        else if(dir==4){
            if((y>5&&x>5&&arr[y][x]==arr[y-5][x-5])||(y<19&&x<19&&arr[y][x]==arr[y+1][x+1])) return;
        }
        cout << arr[y][x] << "\n" << st_y << " " << st_x << "\n";
        exit(0);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    for(int i=1; i<=19; i++){
        for(int j=1; j<=19; j++) cin >> arr[i][j];
    }
    for(int i=1; i<=19; i++){
        for(int j=1; j<=19; j++){
            if((arr[i][j]==1||arr[i][j]==2)&&!ch[i][j])bf(i,j,i,j,1,0);
        }
    }
    cout << 0 << "\n";
    return 0;
}