[백준/Python] 16955번 오목, 이길 수 있을까?

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

문제

구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 작성하시오.

오목에서 승리했다는 것은 자신의 돌이 5개 이상 연속한다는 것이다. 연속은 가로, 세로, 대각선 방향 모두 가능하다.

입력

총 10개의 줄에 바둑판의 상태가 주어진다. '.'는 빈 칸, 'X'는 구사과의 돌, 'O'는 큐브러버의 돌이다.

입력으로 주어지는 바둑판에서 구사과의 돌의 개수와 큐브러버의 돌의 개수는 항상 일치하며, 아직 승자가 정해지지 않은 상태만 입력으로 주어진다.

출력

구사과가 턴을 한 번 가져서 이길 수 있으면 1, 없으면 0을 출력한다.

 

 

코드

input = __import__('sys').stdin.readline
board = []

for i in range(10) :
    board.append(list(input().rstrip()))

def check_left (y, x) :
    x_check = 0
    if x > 0 and board[y][x-1] == 'X':
        x_check += 1
        x_check = x_check + check_left(y, x-1)
    return x_check

def check_right (y, x) :
    x_check = 0
    if x < 9 and board[y][x+1] == 'X':
        x_check += 1
        x_check = x_check + check_right(y, x+1)
    return x_check

def check_up (y, x) :
    x_check = 0
    if y > 0 and board[y-1][x] == 'X':
        x_check += 1
        x_check = x_check + check_up(y-1, x)
    return x_check

def check_down (y, x) :
    x_check = 0
    if y < 9 and board[y+1][x] == 'X':
        x_check += 1
        x_check = x_check + check_down(y+1, x)
    return x_check

def check_upleft (y, x) :
    x_check = 0
    if (y > 0 and x > 0) and board[y-1][x-1] == 'X':
        x_check += 1
        x_check = x_check + check_upleft(y-1, x-1)
    return x_check

def check_upright (y, x) :
    x_check = 0
    if (y > 0 and x < 9) and board[y-1][x+1] == 'X':
        x_check += 1
        x_check = x_check + check_upright(y-1, x+1)
    return x_check

def check_downleft (y, x) :
    x_check = 0
    if (y < 9 and x > 0) and board[y+1][x-1] == 'X':
        x_check += 1
        x_check = x_check + check_downleft(y+1, x-1)
    return x_check

def check_downright (y, x) :
    x_check = 0
    if (y < 9 and x < 9) and board[y+1][x+1] == 'X':
        x_check += 1
        x_check = x_check + check_downright(y+1, x+1)
    return x_check

flag = False

for i in range(10) :
    for j in range(10) :
        if board[i][j] == '.' :
            if check_left(i,j) + check_right(i,j) >= 4 :
                print(1)
                flag = True
                break
            elif check_up(i,j) + check_down(i,j) >= 4 :
                print(1)
                flag = True
                break
            elif check_upleft(i,j) + check_downright(i,j) >= 4 :
                print(1)
                flag = True
                break
            elif check_upright(i,j) + check_downleft(i,j) >= 4 :
                print(1)
                flag = True
                break
    if flag :
        break

if not flag :
    print(0)

 

풀이

빈 칸을 기준으로 각 방향마다 'X' 가 연속으로 몇 개 이어저 있는지 조사한다.
재귀 함수를 이용하여 구현하였고, 예를 들어 왼쪽, 오른쪽에 연속으로 이어져 있는 'X'가 4개 이상이면 이긴다.
매 빈 칸을 조사하는 것은 비효율적이고 'X'가 있는 칸을 조사하는 것이 맞지 않을까 생각했지만
만약 빈 칸의 갯수가 적은 경우, 'X'가 있는 칸을 조사하는 것이 반대로 비효율적이라 생각해 이와 같이 해결했다.