[백준 2615] 오목

• 안녕하세요. BlockDMask 입니다.

• 오늘 푼 문제는 오목 이라는 문제인데요 

• 생각보다 까다로웠습니다.

0. 제목

• 백준 2615 오목

• BOJ 2615 오목

• C언어 오목

• C++ 오목

1. 문제 설명

• 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임입니다.

• 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데
  가로줄은 위에서부터 아래로 1번, 2번, ..., 19번의 번호가 붙고
  세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... , 19번의 번호가 붙습니다.

<그림출처> https://www.acmicpc.net/problem/2615

• 위의 그림에서와 같이 같은 색 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 됩니다.

• 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻합니다.

• 즉, 위의 그림은 검은색이 이긴 경우입니다.
  하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아닙니다.

• 입력으로 바둑판의 어떤 상태가 주어졌을 때, 
  검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 
  판단하는 프로그램을 작성하면 됩니다.

• 단, 검은색과 흰색이 동시에 이기거나 
  검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않습니다.

• 입력 --
  19줄에 각 줄마다 19개의 숫자로 표현
  검은 바둑알 -> 1
  흰 바둑알 -> 2
  알이 놓이지 않는 자리 -> 0
  숫자는 한 칸씩 띄어서 표시 됩니다.

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

• 예시 --
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 1 0 0 0 2 1 2 2 0 0 0 0 0 0 0 0 0 0
  0 0 1 2 0 0 1 2 1 0 0 0 0 0 0 0 0 0 0
  0 0 0 1 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 1 1 2 1 2 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 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
  7 5

2. 풀이 과정

>> 어떤식으로 바둑알을 처리할까? 라는 생각이 먼저 들었습니다.

a. 이중 포문을 이용하여 2차원 배열을 가로로 쭉 스캔 한다고 할때.

검은 돌이 있거나 흰돌이 있으면 거기서 부터 한 방향으로 탐색해서 딱 5개가 되면 게임 끝.

그렇지 않으면 다시 탐색

b-1. 탐색하는 방향은 어떤방향이 있을까? 

아래 그림과 같이 2차원 배열을 --->--> 우측으로 탐색을 한다 했을때

점이 중복되지 않고 체크를 할수 있는 방향은

1) 오른쪽

2) 오른쪽 아래 대각선

3) 아래

4) 왼쪽 아래 대각선

이렇게 4가지 방법 입니다.

b-2. 한 점 y,x에 대해 위에서 말한 4개의 방향에 해당하는

다음 점도 같은 컬러 인 경우! 에 해당 방향으로만! 검사를 쭉쭉합니다.

**관련함수 : solution, omok

c. 5개를 초과하는 경우는 어떻게 처리 할까?

위에 설명 한것 처럼 우측방향으로 차례대로 검색하므로

한 방향에 대해 검사할때 그 방향의 전의 돌이 같은 색이 었는지 검사하면 됩니다.

**관련함수 : isMiddle

d. 승부가 결정 났을때 출력은 어떻게 처리할까?

승부가 결정났을때를 대비하여 각 점들을 vector의 pair 객체로 집어 넣어 좌표를 기억합니다.

sort에 compare 함수를 집어넣어서 문제의 기준에 맞도록 정렬 시킵니다. 

**관련함수 : sort, compare, myPrint

e. 승부가 결정 나지 않는것은 어떻게 처리할까?

승부가 결정나지 않는 다는 것은 전체 맵을 다 돌았을때 까지 연속된 5개의 돌이 없다는 뜻이므로

모든 탐색이 끝난 후 결정 됩니다.

**관련함수 : myPrintFail

3. 소스코드

//https://www.acmicpc.net/problem/2615
//BOJ_2615_omok
 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 20
#define RIGHT 1
#define DOWN 2
#define RIGHTDOWN 3
#define LEFTDOWN 4
using namespace std;
 
int arr[N][N]; //전체맵
 
//입력받음
void input(){
    for(int y=1; y<N; y++){
        for(int x=1; x<N; x++){
            scanf("%d", &arr[y][x]);
        }
    }
}
 
//y,x 가 맵 내부에 있는지 검사
bool isInside(int y, int x){
    return (y>=1 && y<N) && (x>=1 && x<N);
}
 
//가장 왼쪽에 있는 점을 출력하기 위한 정렬 기준
bool compare(pair<int, int> a, pair<int, int> b){
    if(a.second == b.second){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}
 
//누군가 이긴경우 출력
void myPrint(int color, pair<int, int> p){
    cout << color << endl;
    cout << p.first <<" " << p.second;
}
//비긴경우 출력
void myPrintFail(){
    cout <<"0";
}
//처음 검사한건지 = 돌이 가운데 있는것인지 확인
bool isMiddle(int y, int x, int color, int direction){
    if(direction == RIGHT && isInside(y, x-1)){
        if(arr[y][x-1]==color) return false;
    }
    if(direction == DOWN && isInside(y-1, x)){
        if(arr[y-1][x]==color) return false;
    }
    if(direction == RIGHTDOWN && isInside(y-1, x-1)){
        if(arr[y-1][x-1]==color) return false;
    }
    if(direction == LEFTDOWN && isInside(y-1, x+1)){
        if(arr[y-1][x+1]==color) return false;
    }
 
    return true;
}
 
//색이 같은 돌이 한 방향으로 이어져있는가
bool omok(int y, int x, int color, int direction) {
    if(!isMiddle(y, x, color, direction)) return false;
 
    vector<pair<int, int> > v;
    v.push_back(pair<int, int>(y, x));
    int dx = x;
    int dy = y;
 
    if(direction == RIGHT){
        while(arr[dy][++dx] == color){
            v.push_back(pair<int, int>(dy, dx));
        }
    }else if(direction == DOWN){
        while(arr[++dy][dx] == color){
            v.push_back(pair<int, int>(dy, dx));
        }
    }else if(direction == RIGHTDOWN){
        while(arr[++dy][++dx] == color){
            v.push_back(pair<int, int>(dy, dx));
        }
    }else if(direction == LEFTDOWN){
        while(arr[++dy][--dx] == color){
            v.push_back(pair<int, int>(dy, dx));
 
        }
    }
 
    if(v.size() == 5){
        sort(v.begin(), v.end(), compare);
        myPrint(color, v[0]);
        return true;
    }
    return false;
}
 
//가로로 검사하면서 돌이 있으면 solution 호출
bool solution(){
    for(int y=1; y<N; y++){
        for(int x=1; x<N; x++){
            int color = arr[y][x];
            if(color!=0){
                if(color == arr[y][x+1]){
                    if(omok(y, x, color, RIGHT)) return true;
                }
                if(color == arr[y+1][x]) {
                    if(omok(y, x, color, DOWN)) return true;
                }
                if(color == arr[y+1][x+1]) {
                    if(omok(y, x, color, RIGHTDOWN)) return true;
                }
                if(color == arr[y+1][x-1]){
                    if(omok(y, x, color, LEFTDOWN)) return true;
                }
            }
        }
    }
    return false;
}
 
int main(void){
    input();
    if(!solution()) myPrintFail();
    return 0;
}

4. 인증

문제 출처 - https://www.acmicpc.net/problem/2615

감사합니다.

도움이 되었다면 공감버튼 한번 부탁드립니다!