오목( BOJ 2615 )

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

2615번: 오목

 

문제 파악하기

바둑판의 모습이 주어질 때, 흑/백의 승패여부를 판단하는 문제입니다. 종목이 오목이기에 가로, 세로, 대각선 방향으로 연결된 같은 색의 돌이 딱 5개여야하며, 만약 6개 이상 돌이 연결되어 있다면 인정되지 않습니다. 바둑판은 19*19로 이루어졌기에 2차원 배열을 사용하여 바둑판의 모습을 충분히 저장할 수 있으며, 5목인지 판단하면 되기에 놓여진 모든 바둑돌을 하나씩 검사해도 충분히 정답을 빠르게 구할 수 있습니다.

 

문제 해결하기

문제의 정답을 구하기 위해서는 출력해야하는 값에 초점을 맞춰야합니다. 흑/백이 무승부라면 상관없지만, 어느 한 쪽이 승리한다면 우리는 가장 왼쪽 혹은 위쪽의 값을 출력해야 합니다. 따라서, 현재 확인할 바둑돌을 기준으로 오른쪽 방향으로 탐색한다면 조건을 만족하는 바둑돌을 찾았을 시, 바로 탐색을 종료할 수 있습니다. 그럼 오른쪽 방향으로 탐색할 수 있는 방법은 총 몇 가지가 있을까요? 바로 가로방향(오른쪽), 세로방향(아래쪽), 대각선 아래방향(오른쪽+아래쪽), 대각선 위방향(오른쪽+위쪽)까지 총 4가지 있습니다. 이렇게 4가지 방향으로 같은 돌이 연속으로 5개 놓였는지 확인한다면 우리는 정답을 구할 수 있습니다.

 

하지만, 단순히 한 방향으로 5개가 놓였는지 확인하는 위 알고리즘에는 한 가지 큰 문제점이 있습니다. 바로 5목인지 6목 이상인지 제대로 확인하지 못 한다는 것입니다. 만약 바둑돌이 다음과 같이 놓였다면 어떨까요?

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

위 알고리즘에 따르면 가장 왼쪽에 놓인 (3, 3) 돌을 확인할 때에는 6목을 확인하고 정답으로 처리하지 않습니다. 하지만, 바로 오른쪽에 위치한 (3, 4) 돌을 확인할 때에는 왼쪽에 놓은 돌을 확인하지 못한 채, 5목이라고 확인하고 정답으로 처리하게 됩니다. 따라서, 알고리즘의 정확성을 높이기 위해서는 탐색을 진행하는 반대 방향도 확인할 필요가 있습니다. 사실 반대 방향을 모두 확인할 필요는 없고, 바로 옆에 있는 바둑돌만 확인한다면 5목인지 6목인지 확인할 수 있습니다. 이렇게 모든 경우를 파악한다면 우리는 원하는 정답을 찾을 수 있게 됩니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#define NMAX 20
 
int inp[NMAX+1][NMAX+1];
 
int f, cnt;
int x, y, xx, yy;
int dx[4]={0,1,1,-1}, dy[4]={1,0,1,1};
 
bool safe(int x, int y) {
    if(x<1 or y<1 or x>=NMAX or y>=NMAX) return 0;
    else return 1;
}
 
int main() {
    for(int i=1;i<NMAX;i++) {
        for(int j=1;j<NMAX;j++) {
            scanf("%d", &inp[i][j]);
        }
    }
    
    for(int i=1;i<NMAX and !f;i++) {
        for(int j=1;j<NMAX and !f;j++) {
            if(!inp[i][j]) continue;
            
            for(int k=0;k<4 and !f;k++) {
                cnt = 0;
                
                xx = i; yy = j;
                while(safe(xx, yy) and inp[xx][yy] == inp[i][j]) {
                    cnt++;
                    xx += dx[k]; yy += dy[k];
                }
                
                // 6목인지 확인
                if(cnt == 5 and inp[i-dx[k]][j-dy[k]] != inp[i][j]) {
                    f = inp[i][j];
                    x = i; y = j;
                }
            }
        }
    }
    
    printf("%d", f);
    if(f) printf("\n%d %d", x, y);
}
 

후기

6목은 인정되지 않는다는 점에서 나름 생각이 필요한 문제였습니다. 초등 정올 문제답게 문제의 질문은 쉽지만 명확한 알고리즘을 설계하는데 난이도가 있는 문제라고 생각합니다. PS에 입문하는 사람에게 소개할 만한 문제라고 생각합니다.