[알고리즘 풀이 분석] BOJ 2615 오목

짧게나마 여행도 다녀오고~ 크리스마스도 적당히 즐기고 다시 맥을 켜서 공부하려니 집중 최악이고~ ㅎ 그래도 꾸역꾸역 앉아서 해결한 BOJ 2615 오목! 실버 3이지만 괜히 어렵게 생각했다가 저어어기 멀리 돌아왔다.

BOJ 2615 오목

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

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

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

입출력

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

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

나의 풀이

처음엔 습관적으로 BFS를 떠올려서 풀었지만 육목, 칠목은 성공에 해당되지 않는 반례를 해결하지 못했고, 오목이 성공된 경우 가장 왼쪽 위에 존재 하는 돌의 위치를 출력해야 하는 점이 까다로웠다.

좀 더 간단히 구현해도 될 것 같아 새로 알고리즘을 수정하였다.

가장 왼쪽 위 돌을 출력해야 한다는 점을 이용해 판 위에서 검은돌 혹은 흰 돌을 발견하면 해당 돌을 기준으로 오른쪽 위 대각, 오른쪽, 오른쪽 아래 대각, 아랫쪽 으로 탐색을 진행하였다.

이때 탐색을 진행하는 방향 dir 의 반대 방향에 동일한 돌이 있다면 이는 육목 이상의 경우에 해당할 수 있기 때문에 탐색을 진행하지 않는 것이 중요하다!

탐색을 진행하면서 동일 방향에 동일한 색의 돌이 있다면 돌의 갯수 count를 증가 시키고 육목 이상은 모두 동일한 실패이므로 육목까지만 확인한다.

탐색이 끝난 후 count 값이 5가 아니라면 탐색 결과는 false, 5라면 true를 반환한다.

탐색 결과가 true 일 때만 탐색을 시작한 돌의 위치를 함께 출력하면 된다.

코드

cpp

#include <iostream>
#include <vector>

// boj 2615 오목, 구현, 실버 3
using namespace std;

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

int result = 0;
int start_row = -1, start_col = -1;

vector<vector<int>> map(20,vector<int>(20,0));

bool search(int row, int col, int dir){
    int r_dir = (dir+4) % 8;
    int r_row = row + dy[r_dir], r_col = col + dx[r_dir];

    // 시작점 기준 역방향 체크
    if (!(r_row<0||r_row>=19||r_col<0||r_col>=19) && map[r_row][r_col]==map[row][col]) return false;

    // 시작점 기준으로 역방향에 동일한 돌이 없는 경우에만 오목 확인 진행 
    int count = 1;
    for (int i = 1; i <= 5; ++i) {  // 육목 까지 확인 
        int nr = row + dy[dir]*i, nc = col + dx[dir]*i;

        if (nr<0||nr>=19||nc<0||nc>=19) break;
        if (map[nr][nc]==map[row][col]) count++;
        else break;
    }

    if (count==5) return true;
    return false;
}



int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int i = 0; i < 19; ++i) {
        for (int j = 0; j < 19; ++j) {
            cin>>map[i][j];
        }
    }

    for (int i =0; i < 19; ++i) {
        for (int j = 0; j < 19; ++j) {
            if ((map[i][j]==1 || map[i][j]==2)){
                for (int k = 0; k < 4; ++k) {
                    if (search(i, j, k)){
                        result = map[i][j];
                        start_row = i+1, start_col = j+1;
                    }
                }
            }
            if (result != 0) break;
        }
        if (result != 0) break;
    }

    cout<<result<<'\n';
    if (result!=0){
        cout<<start_row<<' '<<start_col<<'\n';
    }

   return 0;
}

swift

import Foundation

var dy = [-1,0,1,1,1,0,-1,-1]
var dx = [1,1,1,0,-1,-1,-1,0]


var result = 0
var win_row = -1, win_col = -1
var board : [[Int]] = Array(repeating: Array(repeating: 0, count: 20), count: 20)

func search(_ row : Int, _ col : Int, _ dir : Int) -> Bool {
    let r_dir = (dir + 4) % 8
    let r_row = row + dy[r_dir], r_col = col + dx[r_dir]
    
    if(r_row<19 && r_row>=0 && r_col<19 && r_col>=0 && board[r_row][r_col] == board[row][col]) {
        return false
    }
    
    var count = 1
    for i in 1...5 {
        let nr = row + dy[dir]*i, nc = col + dx[dir]*i
        
        if(nr<0 || nr>=19 || nc<0 || nc>=19){
            break
        }
        
        if (board[nr][nc] == board[row][col]){
            count += 1
        }else{
            break
        }
    }
    
    if (count == 5){
        return true
    }
    
    return false
}

for i in 0..<19 {
    let nums = readLine()!.components(separatedBy: " ")
    for j in 0..<19 {
        board[i][j] = Int(nums[j])!
    }
}

for i in 0..<19 {
    for j in 0..<19 {
        if (board[i][j] != 0) {
            for k in 0..<4 {
                if (search(i, j, k)){
                    result = board[i][j]
                    win_row = i + 1
                    win_col = j + 1
                }
            }
        }
        if (result != 0){
            break
        }
    }
    if(result != 0){
        break
    }
}

print(result)
if (result != 0){
    print("\(win_row) \(win_col)")
}