[swea 4615-파이썬]재미있는 오셀로 게임

swea 4615 재미있는 오셀로 게임

사용언어 : PYTHON

풀이

방향벡터를 이용하여 모든 방향을 백트래킹 하며 조건에 부합하면 돌의 색상을 변경한다. ( 백트래킹이 맞는건가..? )

조건에 부합한다는 말은 WBBBW 혹은 BWWWWWB와 같은 경우이다.

백트래킹

방향 벡터가 가리키는 방향 한 칸 앞의 색상이 현재 색상과 다르면 flag변수를 1로 바꾸고 한 칸 앞의 색상을 현재 색상으로 변경하고 백트래킹 함수를 수행한다.

이때 변경하기 전 색상을 변수에 저장해두어야 한다. 만약 조건에 부합하지 않는다면 원상복구 해야하기 때문이다.

flag변수 : 2 1 1 1 2 와 같이 한 숫자가 다른 숫자를 감싸는지 확인하기 위해 필요한 변수이다.

재귀함수로 호출한 check()함수가 False를 리턴한다면 조건에 맞지 않는 경우라는 뜻이므로 1로 바꾸었던 flag변수를 0으로 초기화 하고 변경한 색상들을 원상복구 한다.

위 설명을 코드로 나타내면 다음과 같다.

def check(r, c, r_direction, c_direction):
    global flag

    if not (0<= r + r_direction < N and 0<=c + c_direction < N): # 리스트 범위를 벗어나면 False
        return False

    if flag == 1 and l[r + r_direction][c + c_direction] == color: # 한 숫자가 다른 숫자를 감싸는 경우 True를 리턴
        return True

    if l[r + r_direction][c + c_direction] != color and l[r + r_direction][c + c_direction] != 0: # 방향벡터가 가리키는 다음 칸 색상이 현재 색상과 다르고 0이 아니라면 백트래킹을 수행
        flag = 1 # 백트래킹에 진입하였다는 것을 나타내기 위해 1로 변경
        prev_col = l[r + r_direction][c + c_direction] # 원상복구를 위해 원래 색상을 저장
        l[r + r_direction][c + c_direction] = color # 다음 칸의 색상을 현재 색상으로 변경
        if check(r + r_direction, c + c_direction, r_direction, c_direction): # 백트래킹 수행이 True를 리턴한다면 조건에 부합하는 경우
            return True
        flag = 0 # 조건에 부합하지 않았으므로 flag초기화
        l[r + r_direction][c + c_direction] = prev_col # 변경한 색상들을 원래 색상으로 초기화

    return False

이러한 백트래킹을 모든 방향에 대해 수행한다.

코드

def check(r, c, r_direction, c_direction):
    global flag

    if not (0<= r + r_direction < N and 0<=c + c_direction < N):
        return False

    if flag == 1 and l[r + r_direction][c + c_direction] == color:
        return True

    if l[r + r_direction][c + c_direction] != color and l[r + r_direction][c + c_direction] != 0:
        flag = 1
        prev_col = l[r + r_direction][c + c_direction]
        l[r + r_direction][c + c_direction] = color
        if check(r + r_direction, c + c_direction, r_direction, c_direction):
            return True
        flag = 0
        l[r + r_direction][c + c_direction] = prev_col

    return False


T = int(input())

direction = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

for i in range(T):
    N, M = map(int, input().split())
    l = [[0] * N for _ in range(N)]

    l[N // 2 - 1][N // 2 - 1] = l[N // 2][N // 2] = 2  # 백돌 : 2
    l[N // 2 - 1][N // 2] = l[N // 2][N // 2 - 1] = 1  # 흑돌 : 1

    for _ in range(M):
        col, row, color = map(int, input().split())
        l[row - 1][col - 1] = color
        for dr, dc in direction:
            flag = 0
            check(row - 1, col - 1, dr, dc)

    black=sum([p.count(1) for p in l])
    white=sum([p.count(2) for p in l])

    print('#{} {} {}'.format((i+1),black,white))