SWEA 11315. 오목 판정 (Python, DFS, D3)

문제 접근

오목 판정 문제이다. 오목판이 주어지면 지금 상태가 오목성공인지 실패인지를 나타내는 문제다!
오목판이 주어지기 때문에 우선 오목판을 저장해주고 시작하도록 한다.
그리고 오목인지 확인해야 되는데 이 부분을 나는 DFS를 사용해서 풀어줬다.

DFS를 사용한 이유는 방향이 있는 문제이고 모든 오목판을 확인하여 5개 연속인 부분을 찾아야 하기 때문에 DFS또는 BFS를 사용해야 하는데, 한 가지 방향으로 쭉 진행해야 하는 오목의 특성상 DFS를 사용하여 방향을 지정해줄 수 있도록 했다!

• 입력 받기
• DFS로 오목 확인하기
• 출력하기

문제 풀이

입력 받기

pan을 만들고 pan에 오목판의 상태를 입력받는다. 1은 오목돌이 있다는 뜻이고 0은 없다는 뜻이다.

pan = [[0 for i in range(N)] for j in range(N)]
    for i in range(N):
        line = input().rstrip()
        for j, val in enumerate(line):
            if val == '.':
                pan[i][j] = 0
            else:
                pan[i][j] = 1

DFS로 오목 확인하기

DFS를 실행하는 부분이다. 전체 오목판에서 오목돌이 있는 위치에서 DFS를 실행한다.

for i in range(N):
        for j in range(N):
            if pan[i][j]==1:
                for d in range(8):
                    dfs(i,j,d,1)
            if result=="YES":
                break

파라미터로는 오목돌의 위치 i,j와 방향벡터의 인덱스인 d 그리고 라인에 위치한 돌의 개수를 세는 count를 넘겨준다.

만약 이 count가 5가 넘는다면 오목이 완성되었다는 뜻이고 이 때 result에 YES값을 넣어주고 함수를 종료한다.

범위 밖으로 나갔을 경우는 런타임에러를 방지하기 위해 따로 처리해준다.

d방향의 다음 위치에 돌이 있다면 dfs(nx, ny, d, count + 1)로 방향 그대로, 위치 다음 위치로, count는 1 증가하여 재귀를 실행한다.

dx = [0,0,1,1,1,-1,-1,-1]
dy = [1,-1,1,-1,0,1,-1,0]
def dfs(i, j, d, count):
    global result
    if count >= 5:
        result = "YES"
        return
    nx = i + dx[d]
    ny = j + dy[d]
    if nx<0 or ny<0 or nx>=N or ny>=N:
        return
    if pan[nx][ny]==1:
        dfs(nx, ny, d, count + 1)
    else:
        return

출력하기

이제 결과를 출력하는데, result의 초기값은 NO이다. 따라서 만약 5개 이상 연속되는 라인이 없다면 result는 NO로 출력될 것이다.
근데 result가 YES가 된다면 오목이 되는 라인이 최소 1개가 있다는 뜻이므로 다른 돌에 대해서 dfs를 실행하지 않아도 된다.
따라서 이 경우에는 break를 사용하여 종료해준다.

    for i in range(N):
        for j in range(N):
            if pan[i][j]==1:
                for d in range(8):
                    dfs(i,j,d,1)
            if result=="YES":
                break
    print(f'#{test_case} {result}')
                          

제출 코드

dx = [0,0,1,1,1,-1,-1,-1]
dy = [1,-1,1,-1,0,1,-1,0]
def dfs(i, j, d, count):
    global result
    if count >= 5:
        result = "YES"
        return
    nx = i + dx[d]
    ny = j + dy[d]
    if nx<0 or ny<0 or nx>=N or ny>=N:
        return
    if pan[nx][ny]==1:
        dfs(nx, ny, d, count + 1)
    else:
        return
T = int(input())
for test_case in range(1, T + 1):
    result = "NO"
    N = int(input())
    pan = [[0 for i in range(N)] for j in range(N)]
    for i in range(N):
        line = input().rstrip()
        for j, val in enumerate(line):
            if val == '.':
                pan[i][j] = 0
            else:
                pan[i][j] = 1
    for i in range(N):
        for j in range(N):
            if pan[i][j]==1:
                for d in range(8):
                    dfs(i,j,d,1)
            if result=="YES":
                break
    print(f'#{test_case} {result}')