SWEA 4615 재미있는 오셀로 게임 (Python, DFS, D3)

SWEA 4615 재미있는 오셀로 게임 문제 바로가기

문제 접근

돌을 어디에 놓는지는 정해져있기 때문에 돌을 뒀다라는 것은 상하좌우대각선 어딘가에 색깔이 바뀌어야 하는 돌이 있다는 뜻이다.
이 때 바뀌어야 하는 돌이 한방향에만 있을 수도 있고 여러 방향에 있을 수도 있다.

따라서 방향벡터를 사용하여 상하좌우대각선을 확인하여 새로운 돌을 놓을 때 마다 확인하고 돌을 바꿔준다.

문제 풀이

바꿔야할 좌표를 리스트에 넣는 함수 (DFS)

아래의 함수의 파라미터는 a, b는 현재의 위치 color는 돌의 색 d는 방향을 의미한다.
d의 방향으로 하나씩 나아가면서 확인한다. 그 방향에 같은 색의 돌이 없을 때 색깔을 바꾸면 안되기 때문에 Flag를 통해서 이를 확인한다.

dx = [0,0,1,1,-1,-1,1,-1]
dy = [1,-1,0,-1,0,1,1,-1] # 상하좌우대각선
def change(a, b, color, d): # 바꿔야할 좌표를 리스트에 넣는 함수 (DFS)
    global flag # d 방향에 같은 컬러가 있는지 확인하는 flag
    na = a + dx[d]
    nb = b + dy[d]
    if na < 0 or nb < 0 or na >=N or nb >= N: # 범위 밖일 경우 return
        return
    if pan[na][nb] == color: # d 방향에 같은 색의 돌이 있다면 flag를 True로 만들고 함수종료
        flag = True
        return
    if pan[na][nb] != 0 and pan[na][nb] != color: # 다른 color라면 바꿔야할 좌표리스트에 추가하고 1칸 더 진행
        willchange.append((na,nb))
        change(na, nb, color, d)

Flag 처리

flag가 True라면 willchange에 담긴 좌표들을 color로 만들어 준다.

for test_case in range(1, T + 1):
    black, white = 0,0
    N, M = map(int, input().split())
    pan = [[0 for _ in range(N)] for i in range(N)]
    pan[N//2-1][N//2-1] = 2 # 초기값 설정
    pan[N//2][N//2-1] = 1
    pan[N//2-1][N//2] = 1
    pan[N//2][N//2] = 2
    for i in range(M):
        y, x, color = map(int, input().split()) # color == 1? black/ color == 2? white
        pan[x-1][y-1] = color # 색 입력
        for j in range(8): # 방금 놓은 돌을 기준으로 상하좌우대각선 모든 방향에 같은 색의 돌이 있는지 확인
            flag = False # 그 방향에 같은 색의 컬러가 있는지 확인하는 flag
            willchange = [] # 색깔이 바뀌어야하는 좌표들의 리스트
            change(x-1, y-1, color, j) # 바뀌어야하는 좌표들을 찾는 함수
            if flag==True: # 같은 색의 컬러가 있다면 바뀌어야하는 좌표들을 바꿔줌
                for t in willchange:
                    pan[t[0]][t[1]] = color

Count 흑, 백

흑과 백의 개수를 센다.

	for i in range(N): # count하기
        for j in range(N):
            if pan[i][j] == 1:
                black += 1
            elif pan[i][j] == 2:
                white += 1

제출 코드

T = int(input())
dx = [0,0,1,1,-1,-1,1,-1]
dy = [1,-1,0,-1,0,1,1,-1] # 상하좌우대각선
def change(a, b, color, d): # 바꿔야할 좌표를 리스트에 넣는 함수 (DFS)
    global flag # d 방향에 같은 컬러가 있는지 확인하는 flag
    na = a + dx[d]
    nb = b + dy[d]
    if na < 0 or nb < 0 or na >=N or nb >= N:
        return
    if pan[na][nb] == color:
        flag = True
        return
    if pan[na][nb] != 0 and pan[na][nb] != color:
        willchange.append((na,nb))
        change(na, nb, color, d)

for test_case in range(1, T + 1):
    black, white = 0,0
    N, M = map(int, input().split())
    pan = [[0 for _ in range(N)] for i in range(N)]
    pan[N//2-1][N//2-1] = 2 # 초기값 설정
    pan[N//2][N//2-1] = 1
    pan[N//2-1][N//2] = 1
    pan[N//2][N//2] = 2
    for i in range(M):
        y, x, color = map(int, input().split()) # color == 1? black/ color == 2? white
        pan[x-1][y-1] = color # 색 입력
        for j in range(8): # 방금 놓은 돌을 기준으로 상하좌우대각선 모든 방향에 같은 색의 돌이 있는지 확인
            flag = False # 그 방향에 같은 색의 컬러가 있는지 확인하는 flag
            willchange = [] # 색깔이 바뀌어야하는 좌표들의 리스트
            change(x-1, y-1, color, j) # 바뀌어야하는 좌표들을 찾는 함수
            if flag==True: # 같은 색의 컬러가 있다면 바뀌어야하는 좌표들을 바꿔줌
                for t in willchange:
                    pan[t[0]][t[1]] = color
    for i in range(N): # count하기
        for j in range(N):
            if pan[i][j] == 1:
                black += 1
            elif pan[i][j] == 2:
                white += 1
    print(f'#{test_case} {black} {white}')