[백준] 2615번: 오목 풀이 및 해설(C++)

 

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

 

C++로 작성한 백준 문제 2615번 오목에 대한 문제 풀이다.

그리디 알고리즘 문제로 brute force가 문제를 푸는데 필요한 주요 지식이다.

 

 

---

문제 설명

 

문제

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.

 

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.

입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

 

입력

19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.

출력

첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.

 

---

문제 파악하기

1. 오목이 되었는지를 확인하려면 각각 체크하는 좌표를 기준으로 가로, 세로, 대각선으로 오목이 되었는지 확인해야 한다.
2. 그러나 육목일 경우에는 승리했다고 단정지으면 안되고 확인해야 한다.

 

 

---

 

코드 및 설명

#include <iostream>
#include <algorithm>
#include <math.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int arr[27][27]={0,};

int check(int a,int i, int j){
    if(arr[i][j+1]==a && arr[i][j+2]==a && arr[i][j+3]==a && arr[i][j+4]==a && arr[i][j+5]!=a && arr[i][j-1]!=a){
        return a;
    }
    else if(arr[i+1][j]==a && arr[i+2][j]==a && arr[i+3][j]==a && arr[i+4][j]==a && arr[i+5][j]!=a && arr[i-1][j] != a){
          return a;  
    }
    else if(arr[i+1][j+1]==a && arr[i+2][j+2]==a && arr[i+3][j+3]==a && arr[i+4][j+4]==a && arr[i+5][j+5]!=a && arr[i-1][j-1] != a){
        return a;
    }
    else if(arr[i-1][j+1]==a && arr[i-2][j+2]==a && arr[i-3][j+3]==a && arr[i-4][j+4]==a && arr[i-5][j+5]!=a && arr[i+1][j-1] != a){
        return a;
    }
    else{
        return 0;
    }   
    return 0;
}


int main(){

    for(int i=4; i<23; i++){
        for(int j=4; j<23; j++){
            cin>>arr[i][j];
        }
    }
    for(int i=4; i<23; i++){
        for(int j=4; j<23; j++){
            if(arr[i][j]==0){
                continue;
            }
            else if(arr[i][j]==1){
                if(check(1,i,j)==1){
                    printf("1\n%d %d",i-3,j-3);
                    return 0;
                };
            }
            else{
                if(check(2,i,j)==2){
                    printf("2\n%d %d",i-3,j-3);
                    return 0;
                };
            }
        }
    }
    printf("0");
    return 0;
}

 

• 배열의 존재하지 않는 걸 참조하는 IndexError 처리하기 싫어서 그냥 바둑판 자체를 가상으로 상하좌우로 4칸씩 늘려버렸다. 이 경우 확인하는데 있어 따로 IndexError 처리를 안해주어도 된다.

 

---

 

헤매었던 부분

• 엄청나게 많은 실수를 해서 오래걸렸던 문제다. 처음에 그냥 쉽네 하고 풀다가 몇시간 걸려서 풀었다. 
• 헤매기 쉬운 부분으로는
• 1. 육목을 한쪽만 검사하고 반대쪽 그러니까 왼쪽이나 위쪽 방향으론 검사를 안한다거나
• 2. 대각선 양쪽을 다 확인안한다거나
• 3. 위치에 따라서 존재하지 않는 배열 값을 참조하는 IndexError이 발생할 수 있는데 그걸 따로 처리 안해주었다거나 하는 경우들이 있다. 모두 내가 실수했던 부분들이다.

 

---

 

마무리

실수와 반례확인으로 엄청나게 오랜 시간이 걸렸다. 항상 쉽다고 여겨지는 문제일수록 실수에 더 조심하자.