[프로그래머스] 혼자서 하는 틱택토

https://school.programmers.co.kr/learn/courses/30/lessons/160585#

프로그래머스

주어진 틱택토 게임 정보가 정상적으로 진행 중이거나 완료되었는지 확인하는 문제.

 

1. 접근 방법 - 1

아직 시작하지 않았거나, 진행중인 게임 정보가 존재하는 경우가 있으니 선공과 후공 중 누가 이겼는지 판단하기 보다

해당 판의 정보가 올바른지 확인해야 한다.

판을 순회하며 선공 표식과 후공 표식의 개수를 먼저 세본 후

일반적인 경우 1. 후공의 표식이 선공보다 많을 수 없고 2. 선공과 후공의 돌 개수 차이가 1개 이상 날 수 없다.

해당 조건을 만족하는 경우 바로 성립 불가인 0을 리턴한다.

 

2. 접근 방법 - 2

틱택토 게임에서 이기기 위해서는 세로 or 가로 or 대각선을 모두 같은 표식으로 채우면 된다.

일반적으로, 우측 & 우측 하단 & 아래로 가면서 현재 표식과 다음 표식이 일치하면 다음으로 넘어가면서 개수를 센 다음

개수가 3개일 때, 그 판의 시작점이나 끝점이 O면 선공 승리, X인 경우 후공 승리로 계산했다.

선공이 승리일때,  선공 표식과 후공 표식의 개수가 같으면 이미 결판이 난 게임판에 후공이 한 수를 더 둔 것으로, 0을 리턴

후공이 승리일때, 선공 표식의 개수가 후공 표식의 개수보다 많으면 위와 같은 판정으로 0을 리턴한다

 

3. 초기 코드

def solution(board):
    answer = -1
    
    first, second = 0, 0
    
    for row in range(3):
        for col in range(3):
            if board[row][col] == 'O':
                first += 1
            
            elif board[row][col] == "X":
                second += 1
    
    if second > first or abs(first - second) > 1:
        return 0
    
    move = [[0, 1], [1, 0], [1, 1]]
    
    winner = board[0][2] if board[0][2] == board[1][1] == board[2][0] else '.'
    
    for row in range(3):
        for col in range(3):
            if board[row][col] != '.' and winner == '.':
                for ad_r, ad_c in move:
                    counter = 1
                    while 0 <= row + ad_r < 3 and 0 <= col + ad_c < 3:
                        if board[row][col] == board[row + ad_r][col + ad_c]:
                            row, col = row + ad_r, col + ad_c
                            counter += 1
                            
                        else:
                            break
                    
                    if counter == 3:
                        winner = board[row][col]
                        break
                    
    
    if winner == 'O' and first == second:
        return 0
    
    elif winner == 'X' and first > second:
        return 0
    
    return 1

winner 변수를 가장 먼서 정의한 이유

- 설계한 탐색 방향은 전반적으로 우측 하단으로 향한다. 하지만 해당 방법으로는 캐치하지 못하는 하나의 케이스가 존재한다.

" / " 방향으로 이뤄진 승리 케이스인데, 이를 탐색하기 위해서 방향을 추가하는 것 보다는

저 케이스 하나만 따로 보고 승자를 먼저 판단하도록 구현했다.

 

4. 추가 케이스 처리

위 코드는 모든 케이스를 통과하지 못한다.

코드라인 중, if board[row][col] != '.' and winner == '.' 에서 그 원인을 찾을 수 있었는데

게임판 좌상단에서 우하단으로 순차적으로 탐색하다가, 승리자가 나오면 더 이상 탐색을 하지 않는 다는 것이 문제였다.

따라서 위 코드는 아래 케이스를 통과할 수 없다.

XXX
.  .  .
OOO

해당 게임은 이미 선공이 이긴 상태에서 종료되어야 하나, 후공이 한 수를 더 둔 케이스로 0이 리턴되어야 하지만

코드 로직대로라면 처음 탐색 시 X를 승리자로 판단하고 탐색을 종료, 선공 표식과 개수가 같은 경우를 인정하여 1을 리턴한다.

 

5. 코드 수정

한쪽의 승리가 확정된다고 해서 탐색을 중단하는 것은 위험한 일이므로 선공 승리 여부와 후공 승리 여부를 같이 판단하도록 했다.

양쪽이 모두 승리하는 케이스는 존재할 수 없으므로, 해당 경우에는 0을 리턴하도록 추가. 나머지 케이스는 기존과 유사하게 변경하였다.

이후 채점 결과를 보다가 계산이 꼬일 수 있는 부분도 추가적으로 수정했다.

O나 X가 맞을 때, 다음 방향을 계산하는 것이 for 문의 row, col 과 중복되어 계산이 꼬인 것을 확인하고

해당 변수를 s_row, s_col로 변경하였다.

 

6. 제출 코드

def solution(board):
    answer = -1
    
    first, second = 0, 0
    
    for row in range(3):
        for col in range(3):
            if board[row][col] == 'O':
                first += 1
            
            elif board[row][col] == "X":
                second += 1
    
    if second > first or abs(first - second) > 1:
        return 0
    
    move = [[0, 1], [1, 0], [1, 1]]
    
    first_win, second_win = False, False
    
    winner = board[0][2] if board[0][2] == board[1][1] == board[2][0] else '.'
    
    if winner == 'O':
        first_win = True
    
    elif winner == 'X':
        second_win = True
    
    for s_row in range(3):
        for s_col in range(3):
            if board[s_row][s_col] != '.':
                row, col = s_row, s_col
                for ad_r, ad_c in move:
                    counter = 1
                    while 0 <= row + ad_r < 3 and 0 <= col + ad_c < 3:
                        if board[row][col] == board[row + ad_r][col + ad_c]:
                            row, col = row + ad_r, col + ad_c
                            counter += 1
                            
                        else:
                            break
                    
                    if counter == 3:
                        if board[row][col] == 'O':
                            first_win = True
                        
                        if board[row][col] == 'X':
                            second_win = True
                        
                        break
    # print(first_win, second_win)
    if first_win and second_win:
        return 0
    
    if first_win and first == second:
        return 0
    
    if second_win and first > second:
        return 0
    
    return 1