[SWEA 코딩] 오목 판정 - PYTHON #11315

# i,j, 이동 방향, 현재까지 연속된 돌의 숫자
def dfs(i, j, dir, cnt):
    global dfs_break
    
    # 탈출조건, 연속된 돌의 개수가 5 이상이면
    if cnt >= 5:
        
        # 이 후 추가적인 탐색을 피하기 위해 변경
        dfs_break = 1
        return

    # 범위 벗어나지 않으면
    if 0 <= i + x[dir] < n and 0 <= j + y[dir] < n:
        
        # 다음 위치에 돌이 놓여 있으면
        if board[i + x[dir]][j + y[dir]] == 'o':
            dfs(i + x[dir],j + y[dir],dir,cnt+1)

        else:
            return

    else:
        return


T = int(input())

# →, ↘, ↓, ↙
x = [0, 1, 1, 1]
y = [1, 1, 0, -1]

for tc in range(1, 1 + T):

    # 오목판 크기
    n = int(input())

    # 오목판
    board = [list(map(str, input())) for _ in range(n)]

    # 한 번 찾은 후, 추가적인 탐색을 피하기 위한 기준
    dfs_break = 0

    for q in range(n):
        
        # 이미 5개 이상인 경우 있으면
        if dfs_break == 1:
            break

        for w in range(n):

            # 이미 5개 이상인 경우 있으면
            if dfs_break == 1:
                break

            # 돌이 놓여있는 곳이면
            if board[q][w] == 'o':
                
                # 방향 탐색
                for e in range(4):
                    
                    # → 방향이면
                    if e == 0:
                        
                        # 현재 위치에서 오른쪽으로 움직일 수 있는 범위가 5 이상인 경우
                        # 5보다 작으면 탐색할 필요 없음
                        if n-w >= 5:
                            
                            # q,w,이동 방향,현재까지 연속해서 놓인 돌의 개수
                            dfs(q,w,e,1)

                    # ↘ 방향이면
                    elif e == 1:
                        
                        # 현재 위치에서 오른쪽, 아래로 움직일 수 있는 범위가 5 이상인 경우

                        if n-w >= 5 and n-q >= 5:
                            dfs(q,w,e,1)

                    # ↓ 방향이면
                    elif e == 2:
                        
                        # 현재 위치에서 아래로 움직일 수 있는 범위가 5 이상인 경우
                        if n-q >= 5:
                            dfs(q,w,e,1)

                    # ↙ 방향이면
                    else:
                        
                        # 현재 위치에서 아래로 움직일 수 있는 범위가 5 이상인 경우
                        # 현재 위치에서 왼쪽으로 움직일 수 있는 범위가 4 이상인 경우
                        # ex) w가 4이면 0,1,2,3,4 최대 5개 가능
                        if n-q >= 5 and w >= 4:
                            dfs(q,w,e,1)

                    # 이미 5개 이상인 경우 있으면
                    if dfs_break == 1:
                        break

    # 5개 이상인 경우 존재하면
    if dfs_break == 1:
        print('#{} {}'.format(tc,'YES'))

    # 존재하지 않으면
    else:
        print('#{} {}'.format(tc,'NO'))

 

그 외

문제 풀이를 위한 아이디어

 

1. 백트래킹이 필수적이라 판단

 

2. 불필요한 연산이 많아서 비효율적이라 생각했기 때문

 

사용한 백트래킹 방법

1. 이동할 방향에 존재할 수 있는 최대 돌의 개수를 계산

 

2. 한 번 5개 이상인 경우를 찾으면 탐색을 중단하기

 

3. 이동 가능한 방향은 8 방향이지만, 차례대로 탐색할 경우, →, ↘, ↓, ↙ 4 방향만 탐색하면 됨

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다