[SWEA][D3][#11315] 오목 판정

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

N X N 크기의 판이 있다. 판의 각 칸에는 돌이 있거나 없을 수 있다. 돌이 가로, 세로, 대각선 중 하나의 방향으로 다섯 개 이상 연속한 부분이 있는지 없는지 판정하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(5 ≤ N ≤ 20)이 주어진다.

다음 N개의 줄의 각 줄에는 길이 N인 문자열이 주어진다. 각 문자는 ‘o’또는 ‘.’으로, ‘o’는 돌이 있는 칸을 의미하고, ‘.’는 돌이 없는 칸을 의미한다.

출력

각 테스트 케이스 마다 돌이 다섯 개 이상 연속한 부분이 있으면 “YES”를, 아니면 “NO”를 출력한다.

예제

입력

4
5
....o
...o.
..o..
.o...
o....
5
...o.
ooooo
...o.
...o.
.....
5
.o.oo
oo.oo
.oo..
.o...
.o...
5
.o.o.
o.o.o
.o.o.
o.o.o
.o.o.

출력

#1 YES
#2 YES
#3 YES
#4 NO

My Sol

def Omok(mat, ni, nj, di, dj):
    cnt = -1
    ii, jj = ni, nj
    while mat[ii][jj] == 'o':
        ii += di
        jj += dj
        cnt += 1

    ii, jj = ni, nj
    while mat[ii][jj] == 'o':
        ii -= di
        jj -= dj
        cnt += 1

    if cnt >= 5:
        return 1
    return 0

def OmokMain(mat, ni, nj):
    didj = [[1,0], [0,1], [1,1], [-1,1]]
    flag = 0
    for di, dj in didj:
        if flag:
            return 1
        if Omok(mat, ni, nj, di, dj):
            flag = 1
    if flag:
        return 1
    return 0

T = int(input())
for tc in range(T):
    N = int(input())
    mat = [['.']*(N+2)]
    mat += [['.']+list(input())+['.'] for _ in range(N)]
    mat += [['.']*(N+2)]

    flag = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            if mat[i][j]=='o':
                if OmokMain(mat, i, j):
                    flag = 1
            if flag:
                break
        if flag:
            break

    ans = 'NO'
    if flag:
        ans = 'YES'
    print(f'#{tc+1} {ans}')

NxN 배열의 각 칸들을 모두 순회하며 해당 칸에서 뻗쳐나가는 가로선, 세로선, 각각의 대각선 모두 카운트하여 5가 넘으면 오목이므로 YES를 출력하는 것이다. NxN 배열의 가장자리에 .을 둘러 ‘o’가 아닌 영역으로 설정하였고, 함수에서 마음 편하게 ‘o’인 동안 cnt를 올리는 식으로 작성하였다.

벡터를 사용하여 가로선일 때 왼쪽인 때랑 오른쪽인 때, 세로선일 때는 위쪽과 아래쪽, 이런 식으로 경우를 나누어 벡터를 더하고 빼주며 오목을 판단했고, flag를 적극활용해서 어떤 절차 중에 오목을 캐치하면 모든 반복을 중단하고 1을 반환하고 이를 함수를 호출한 곳에서도 받아서 바로 YES를 출력할 수 있도록 하였다.

코드를 조금 더 컴팩트하게 짤 수 있을 것도 같지만, 우선 구현과 정확성에 신경을 썼다. 나름 중복 코드 없이 잘 해결한 것 같다.

고찰

어차피 모든 NxN을 순회하면 중간이 아닌 끝점에서부터 세는 경우가 있을테니까 굳이 양쪽을 안 세어줘도 괜찮았다는 사실을 알게 되었다!!

결과

PASS