[백준 2615번/c++] 오목

문제

바둑판의 상태가 주어지면 흰색 또는 검은색 중 무슨색이 이겼는지 판단

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

2615번: 오목

조건

• 바둑판의 크기는 19 * 19
• 같은 색의 바둑알이 연속적으로 5알이 놓이면 이긴다.
  • 6알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다! -> 놓치기 쉬움

 

입출력

입력

• 바둑판이 19 * 19로 숫자로 표시된다.
  • 검은 바둑알: 1, 흰 바둑알: 2, 알이 놓이지 않는 자리: 0

출력

• 승부가 결정이 나는 경우
  • 검정 바둑알 승: 1 출력
  • 흰 바둑알 승: 2 출력
  • 연속된 다섯개의 바둑알 중에서 가장 왼쪽(세로로 놓인 경우 가장 위)의 가로줄 번호와 세로줄 번호를 순서대로 출력
• 승부가 결정이 나지 않는 경우
  • 0 출력

 

---

접근

19*19 배열을 모두 탐색하며 바둑알이 놓여 있는 경우 가로, 세로, 대각선 방향에 대해 각각 같은 색의 바둑알을 세어 5개가 되는 경우를 찾는다.

 

노란색, 핑크색, 주황색, 파란색

4개의 선 모양 중 하나로 같은 색의 바둑알이 5개 놓이면 이기게 된다.

 

초록색 기준점에 대하여 각각의 방향으로 이동하기 위해서는 아래 표와 같이 좌표 값이 더해져야 한다.

(-1, -1)	(-1, 0)	(-1, 1)
(0, -1)	기준점 (0, 0)	(0, 1)
(1, -1)	(1, 0)	(1, 1)

 

 

---

코드 구현

가로, 세로, 대각선 방향으로 탐색하기 위해, dx, dy 배열을 두었다.

이 때, 기준점에 대해 두 방향으로 탐색해야 하므로

2번 방향으로 같은 바둑알의 색이 연속되는 경우에 바둑알의 개수를 세어주고,

2번 방향의 좌표에 -1을 곱하여 1번 방향에 대해서도

똑같이 같은 바둑알의 색이 연속되는 경우에 바둑알의 개수를 세어준다.

 

이렇게 양방향으로 세어주어야, 6개 이상 연속되는 경우를 구분할 수 있다!

---

성공 코드(내 코드)

#include <iostream>
#include <vector>
using namespace std;

int dx[4]={0, 1, 1, 1};
int dy[4]={1, 1, 0, -1};

int main(){
    // freopen("input.txt", "rt", stdin);
    int go_board_size=19, color, cnt;
    vector<vector<int> > go_board(20, vector<int>(20, 0));
    for(int i=1; i<=go_board_size; i++){
        for(int j=1; j<=go_board_size; j++){
            cin >> go_board[i][j];
        }
    }
    // 바둑판 탐색
    for(int i=1; i<=go_board_size; i++){
        for(int j=1; j<=go_board_size; j++){
            if(go_board[i][j]>0){ // 바둑알이 있는 경우
                color=go_board[i][j];
                // 가로, 세로, / 대각선, \ 대각선에 대해 탐색
                for(int k=0; k<4; k++){
                    cnt=1;
                    int xx=i-dx[k], yy=j-dy[k];
                    // 왼쪽 또는 위로
                    while(xx>=1 && xx<=go_board_size && yy>=1 && yy<=go_board_size){
                        if(go_board[xx][yy]==color){
                            xx-=dx[k]; yy-=dy[k];
                            cnt++;
                        } else{
                            break;
                        }
                    }
                    // 오른쪽 또는 아래로
                    xx=i+dx[k], yy=j+dy[k];
                    while(xx>=1 && xx<=go_board_size && yy>=1 && yy<=go_board_size){
                        if(go_board[xx][yy]==color){
                            xx+=dx[k]; yy+=dy[k];
                            cnt++;
                        } else{
                            break;
                        }
                    }
                    // 같은 색의 바둑돌이 5개가 연속되면
                    if(cnt==5){
                        cout << color << "\n"; // 색상 출력
                        if(yy<j){ // 마지막에 탐색한 위치가 탐색을 시작한 위치보다 왼쪽에 있으면
                            cout << xx-dx[k] << " " << yy-dy[k]; // while 문을 나오기 전 +dx[k], +dy[k]가 된 상태이므로 빼서 출력
                        } else{
                            cout << i << " " << j;
                        }
                        return 0;
                    }
                }
            }
        }
    }
    cout << 0;

    return 0;
}

---

후기

문제 접근 후 코드 구현 후에 계속 틀려서, 여러 케이스들을 넣어보며 고려하지 못했던 부분들을 찾아 코드를 수정하는 과정을 반복했다. 맨처음에는 바둑판을 1줄에서 19줄까지 차례로 탐색하므로, 가로, 세로, / 대각선, \ 대각선에 대하여 각각 양방향 탐색을 하지 않아도 된다고 생각하여 오른쪽 또는 아래로만 같은색 바둑알의 개수를 세었다.(왼쪽 또는 위로는 바둑판을 탐색하며 거쳐왔으므로 고려하지 않아도 된다고 생각하였다.) 이렇게 하니 6개 이상 연속되는 경우를 잡아내지 못했고, 계속 틀리게 되었다. 이 점을 찾아내는데 시간이 걸렸던 문제였다.