[백준 7682번] 틱택토

7682번: 틱택토

area = [["."]*3 for _ in range(3)]

cases = set()

def check_is_full():
    is_full = True
    
    for i in range(3):
        for j in range(3):
            if area[i][j] == '.':
                is_full = False

    return is_full

def check_end():

    if check_is_full():
        return True

    if (area[0][0] == area[0][1] == area[0][2] and area[0][0] != ".") or (area[1][0] == area[1][1] == area[1][2] and area[1][0] != '.') or (area[2][0] == area[2][1] == area[2][2] and area[2][0] != '.') or (area[0][0] == area[1][0] == area[2][0] and area[0][0] != '.') or (area[0][1] == area[1][1] == area[2][1] and area[0][1] != '.') or (area[0][2] == area[1][2] == area[2][2] and area[0][2] != '.') or (area[0][0] == area[1][1] == area[2][2] and area[0][0] !='.') or (area[0][2] == area[1][1] == area[2][0] and area[0][2] != '.') :
        return True
    
    return False


def dfs(current):
    
    if check_end():
        temp = ""
        for row in area:
            temp += "".join(row)
        cases.add(temp)
        return
    
    for i in range(3):
        for j in range(3):
            if area[i][j] == '.':
                area[i][j] = current
                if current == "X":
                    dfs("O")
                else:
                    dfs("X")
                area[i][j] = "."

dfs("X")


while True:
    
    string = input()

    if string == 'end':
        break

    if string in cases:
        print("valid")
    else:
        print("invalid")

이번 문제는 입력으로 주어진 게임판이 틱택토 게임에서 발생할 수 있는 상태인지 구별하는 문제이다.

 

이 문제가 조금 까다로웠던 이유는, 단순히 게임 종료 조건(가로/세로/대각선 3칸 동일)을 만족하는지 구하는 것이 아니라, X부터 O와 번갈아가며 말을 놓았을 때 발생할 수 있는 경우인지 판별하는 문제였기 때문이다.

 

따라서 본인은 DFS를 사용하여 X를 처음 놓는 순간부터 종료되는 시점(check_end)까지 모든 경우의 수를 다 탐색하고, 종료 조건에 만족하면 해당 게임판을 문자열로 변환하여 저장한 뒤 각 입력과 비교해주는 방식으로 풀이하였다.

 

DFS와 구현을 연습해볼 수 있었던 좋은 문제였다 :)