2580 스도쿠에 이어서, 백트래킹 문제.
같은 배열에 대해 공유해가며 값을 수정할 수 있다는 것에 대해 익숙해지기 위해 골랐다.
문제 요약
- 여러개의 테스트 케이스로 입력을 받는다.
- 3x3짜리 틱택토 게임 보드가 한 줄로 들어온다. 각 칸은
O,X,.로 존재하는데,.의 경우 아직 O나 X를 놓지 않은 빈 공간을 의미한다. - 주어진 게임 보드는 게임이 종료된 후의 상태로, 이 보드가 정상적으로 게임이 종료되었을 때의 상태인지 검사하여 valid, unvalid를 출력한다.
풀이
백트래킹으로 푼다는 것을 인지하고 선택한 문제여서, 백트래킹으로 접근해보았다. 이 게임이 유효한 게임인지 확인하기 위해 X, O가 번갈아서 패를 놓는 것을 시뮬레이션한다고 생각했다.
게임 종료 조건
- 패 3개가 연결되어 누군가의 승리로 끝
- 승리가 정해지지 않았지만 9개의 칸이 모두 참
유효하지 않은 조건
- 주어진 상태가 완성되지 않았는데 패 3개가 연결 되어 게임이 종료
- 주어진 상태가 완성되지 않았는데 패를 놓을 수 없음(놓아야하는 O가 남았는데 놓을 수 있는 X가 없음. 즉, O가 X의 수보다 많음)
- 9개의 칸이 가득차지 않았고, 패 3개가 연결되지 않은 게임 보드
승리 검사
누가 승리했는지를 어떻게 검사할지 고민을 했다. 좌표를 비교해가며 검사를 할까 고민했는데, 생각해보니 누군가가 승리하는 경우 자체가 한정적이었다.
O와 X에 관계없이, 어느 하나가 1의 위치에 배열되기만해도 이 게임은 그 기호의 승리이다.
위와 같은 경우가 존재할 경우, O가 8번째 배열을 만족해서 이 게임은 O의 승리로 끝난다.
즉, and 연산이다.
다시 위의 보드로 돌아오면, O를 1, X를 0으로 대치하면 001110100으로 나타낼 수 있다.
위의 승리 조건들은 각각 다음과 같이 나타낼 수 있다.
111000000
000111000
000000111
100010001
001010100
100100100
010010010
001001001귀찮게 좌표 따질 필요 없이, 현재 보드와 승리 조건 보드들을 and 연산으로 비교하면 끝.
백트래킹
검사하는 과정을 isEnd라는 함수로 만들어두었기 때문에 백트래킹만 수행하면 된다.
def proceed(level, board, compare) : # compare는 현재 놓으려는 문자. (X or O)
if level == len(O_coor) + len(X_coor) : # level은 현재 검사하는 depth. 모든 O와 X가 나왔는지 검사
if isEnd(board, 'O') or isEnd(board, 'X') : # 둘 중 하나가 종료되었으면 정상종료
return True
elif level == 9: # 승부에 관계없이 모든 칸이 찼으면 정상 종료
return True
else : # 그렇지 않으면 비정상 종료
return False
# 모든 O와 X가 놓아지지 않았는데 승부가 결정되었으면 비정상 종료
if isEnd(board, 'O') or isEnd(board, 'X') :
return False
# 현재 검사하는 문자에 따라 배열을 바꾸어 줌.
curCoor = X_coor
if compare == 'O' :
curCoor = O_coor
for i in curCoor :
if board[i] == '.' :
board[i] = compare
if proceed(level + 1, board, reverse(compare)) :
return True
board[i] = '.'O_coor과 X_coor은 주어진 보드에서 O와 X의 좌표를 각각 list로 저장한 것이다. 위의 그림의 예시라면 O_coor=[2, 3, 4, 6], X_coor=[1, 5, 7, 9]이다.
마지막 for문은, 설명을 덧붙히자면 현재 문자가 들어갈 수 있는 위치들에 대해 현재 문자를 넣고 재귀를 수행한다.
[. . . . . . . . .]가 처음에 들어오면
[. X . . . . . . .]
[. X O . . . . . .]
...
로 갱신되는 것이다. 그러다가 만일 invalid할 경우 해당 단계를 종료하고 이전으로 돌아온다.
마찬가지로 DFS로 수행하기 때문에, 현재의 배열을 모든 단계의 함수들이 공유하며, 값을 바꾸더라도 함수 종료 후 다시 .으로 바꾸어준다면 다른 단계의 함수에 영향을 미치지 않는다.
모든 경우를 수행하고 만일 주어진 배열의 게임 보드가 한번이라도 완성된다면, 그 경우는 valid한 경우이므로 valid를 출력한다.
