[Python] 프로그래머스 레벨2 - 혼자서 하는 틱택토

문제 설명

틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다.

할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.

• 혼자서 선공과 후공을 둘 다 맡는다.
• 틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다.

틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면 다시 3x3 빈칸을 그린 뒤 다시 게임을 반복했습니다. 그렇게 틱택토 수 십 판을 했더니 머쓱이는 게임 도중에 다음과 같이 규칙을 어기는 실수를 했을 수도 있습니다.

• "O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
• 선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.

게임 도중 게임판을 본 어느 순간 머쓱이는 본인이 실수를 했는지 의문이 생겼습니다. 혼자서 틱택토를 했기에 게임하는 과정을 지켜본 사람이 없어 이를 알 수는 없습니다. 그러나 게임판만 봤을 때 실제로 틱택토 규칙을 지켜서 진행했을 때 나올 수 있는 상황인지는 판단할 수 있을 것 같고 문제가 없다면 게임을 이어서 하려고 합니다.

머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가 매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

제한사항

• board의 길이 = board[i]의 길이 = 3
  • board의 원소는 모두 "O", "X", "."으로만 이루어져 있습니다.
• board[i][j]는 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
  • "."은 빈칸을, "O"와 "X"는 해당 문자로 칸이 표시되어 있다는 의미입니다.

---

나의 풀이

사실 문제 유형이 감이 안와서 dfs 로 풀어야하나? 그렇다면 어떻게 풀어야하지? 고민을 많이 했다.

그래도 잘 모르겠어서 그럼 일단 생각나는 대로 풀어봤다.

인간이라면 일단 주어진 board 가 정상적이다 비정상적이다를 어떻게 판단할 것인지를 생각해봤다.

• 우선 O와 X 의 갯수를 세보고, 선공과 후공이 번갈아가면서 놨는지를 체크할 것이다.
• 가로, 세로, 대각선 중에 O나 X 가 같은 표시를 만들어낸게 있는지를 확인했다.

 

1. 우선 O와 X 의 갯수를 세보고, 선공과 후공이 번갈아가면서 놨는지를 체크할 것이다.

def solution(board):
    o_count = 0
    x_count = 0

    for i in range(3):
        for j in range(3):
            if board[i][j] == 'O':
                o_count += 1
            elif board[i][j] == 'X':
                x_count += 1

    if x_count - o_count > 0 or o_count - x_count > 1:
        return 0

- 완전탐색을 통해 board에 놓여진 O와 X의 갯수를 count 했다. 어차피 board의 크기는 3*3 으로 매우 작기 때문에 완전 탐색을 해도 괜찮을 것 같다고 판단했다.

- O가 먼저 놓기 때문에 O가 X 보다 하나 많이 놓거나, O와 X 의 갯수가 같아야 한다. 그러므로 O는 X 보다 1개 이상 많아선 안되고, X의 갯수가 O 보다 많아서도 안된다.

 

2. 가로, 세로, 대각선 중에 O나 X 가 같은 표시를 만들어낸게 있는지를 확인했다.

def checkFinished(board, now):
    # 현재 위치 가로/세로 확인
    for i in range(3):
        i_cnt = 0       # 가로
        j_cnt = 0       # 세로
        for j in range(3):
            if board[i][j] == now:
                i_cnt += 1
            if board[j][i] == now:
                j_cnt += 1
        if i_cnt == 3:
            return True
        if j_cnt == 3:
            return True

    # 대각선 확인
    # 왼->오
    cnt = 0
    for i in range(3):
        if board[i][i] == now:
            cnt += 1
    if cnt == 3:
        return True
    # 오->왼 대각선
    cnt = 0
    for i in range(3):
        if board[i][2-i] == now:
            cnt += 1
    if cnt == 3:
        return True
    return False

1. 하나의 이중 for문 내에서 가로/세로로 완성된 부분이 있는지 확인했다.

- 가로로 같은 표시가 완성됐는지 확인하기 위해 0행, 1행, 2행의 가로를 확인했다.

- 세로로 같은 표시가 완성됐는지 확인하기 위해 0열, 1열, 2열의 세로방향을 확인했다.

 

2. 대각선은 왼쪽에서 오른쪽 방향과 오른쪽에서 왼쪽방향으로 2가지의 대각선이 있다.

① (0, 0) > (1, 1) > (2, 2) 으로 탐색하면 왼쪽에서 오른쪽 방향으로,

② (0, 3) > (1, 1) > (2, 0) 으로 탐색하면 오른쪽에서 왼쪽 방향의 대각선으로 완성됐는지 확인할 수 있다.

for 을 통해 각 인덱스에 접근하려면 for i in range(3) 만으로도 가능하다. 각 행은 i 로 열은 2-i면 오른쪽>왼쪽방향 대각선 칸에 접근할 수 있다.

checkFinished 함수 호출

    if checkFinished(board, 'O'):
        if o_count == x_count:
            return 0  
    if checkFinished(board, 'X'):
        if o_count > x_count:
            return 0

- solution 함수에서 해당 함수를 호출해서 완성된 부분이 있는지 체크하고, valid한 갯수인지 체크했다. 

- O가 이미 완성됐는데 O와 X의 갯수가 같은 경우는 O가 완성됐음에도 X를 표시한거니까 잘못된 경우이기 때문에 0을 리턴했다.

- X가 완성됐는데 X보다 O의 갯수가 많은 경우는 X가 완성됐음에도 O를 표시한거기 때문에 잘못된 경우이다.

---

최종 소스

def checkFinished(board, now):
    # 현재 위치 가로/세로 확인
    for i in range(3):
        i_cnt = 0       # 가로
        j_cnt = 0       # 세로
        for j in range(3):
            if board[i][j] == now:
                i_cnt += 1
            if board[j][i] == now:
                j_cnt += 1
        if i_cnt == 3:
            return True
        if j_cnt == 3:
            return True

    # 대각선 확인
    # 왼->오
    cnt = 0
    for i in range(3):
        if board[i][i] == now:
            cnt += 1
    if cnt == 3:
        return True
    # 오->왼 대각선
    cnt = 0
    for i in range(3):
        if board[i][2-i] == now:
            cnt += 1
    if cnt == 3:
        return True
    return False

def solution(board):
    o_count = 0
    x_count = 0

    for i in range(3):
        for j in range(3):
            if board[i][j] == 'O':
                o_count += 1
            elif board[i][j] == 'X':
                x_count += 1

    if x_count - o_count > 0 or o_count - x_count > 1:
        return 0  
    if checkFinished(board, 'O'):
        if o_count == x_count:
            return 0  
    if checkFinished(board, 'X'):
        if o_count > x_count:
            return 0  

    return 1

- 위와 같이 하면 성공이다. 야호!👍

- 그런데 무식하게 풀었다는 느낌이 지워지지 않는다. 이게 맞나?! 더 좋은 방법이 있을 것만 같다.

---

실패한거 되돌아보기

맨 처음에는 solution 함수의

if x_count - o_count > 0 or o_count - x_count > 1:
    return False

이 부분을 

if o_count < x_count:
    return False

이렇게 했었다. 그랬더닌 반례가 있었는지 테스트 케이스 9, 10, 37, 40, 44에서 실패가 떴다.

- O를 X보다 더 많이 놨을 경우를 고려하지 못했다.

예를 들어 이런 경우..

---

아무튼 성공했다... 조금은 무식한 방법일지 모르겠지만.. 새로운 문제라 그런지 구글링해도 다른 사람들의 풀이가 없어서 그래도 풀어봐야지 하고 잡고 있었더니 그래도 풀어서 아주 뿌듯하다...🥹

언젠간 다른 사람들의 풀이가 뜨면 그때 다시 좋은 방법 공부해서 풀어봐야겠다!

 

 

- 

문제가 있을 경우 댓글로 알려주시길 바랍니다.