[swea] 4615 재미있는 오셀로 게임

재미있는 문제라서 들고 왔습니다. 

 

1. 해당 방향으로 쭉 탐색하면서 해당 칸 놓는 돌로 변경.

2.1 만약 끝에 같은 돌이 없다면, 다시 원래대로.

2.2 만약 끝에 같은 돌이 있다면, 그대로 유지

 

dfs를 이용해서 풀었습니다.

t = int(input())
directions = [[0,1],[0,-1], [1,0],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]]
def dfs(board, y,x, dy, dx, c, n):
    if y < 0 or x < 0 or y >= n or x >= n:
        return True
    if board[y][x] == 0:
        return True
    if board[y][x] == c and board[y][x] != 0:
        return False
        
    tmp = board[y][x]
    board[y][x] = c
    flag = dfs(board, y + dy, x + dx, dy, dx, c, n)
    
    if flag:
        board[y][x] = tmp
        
    return flag
for tt in range(1,t+1):
    n,m = map(int, input().split())
    
    board = [[0 for _ in range(n)] for _ in range(n)]
    board[n//2-1][n//2-1] = 2
    board[n//2][n//2] = 2
    board[n//2-1][n//2] = 1
    board[n//2][n//2-1] = 1
    
    for _ in range(m):
        x,y,c = map(int, input().split())
        y -= 1
        x -= 1
        board[y][x] = c
        
        for dy,dx in directions:
            ny = y+dy
            nx = x+dx
            dfs(board,ny,nx,dy,dx,c,n)
            
    b_cnt = 0
    w_cnt = 0
    
    for i in range(n):
        for j in range(n):
            if board[i][j] == 2:
                w_cnt += 1
            elif board[i][j] == 1:
                b_cnt += 1
                
    print('#{} {} {}'.format(tt, b_cnt, w_cnt))

 

 

*앞으로는 문제풀이 글은 자주 업로드하지 않을 예정입니다.