[BOJ][⚪2][백준#02615] 오목

문제 출처

BAEKJOON Online Judge #2615

문제

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, … ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, … 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다. 입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

입력

19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.

출력

첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.

예제

입력

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0
0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

출력

1
3 2

My Sol

def main():
    for j in range(19):
        for i in range(19):
            if mat[i][j]:
                nv = mat[i][j]
                ni, nj = i, j
                if check4(nv, ni, nj):
                    return nv, ni+1, nj+1
    return 0, 0, 0

def check4(nv, ni, nj):
    didj = [(0,1),(1,0),(1,1),(1,-1)]
    for di, dj in didj:
        if check(nv, ni, nj, di, dj) == 5:
            return 1
    return 0

def check(nv, ni, nj, di, dj):
    a = 1
    while (0<=ni-a*di<19) and (0<=nj-a*dj<19) and (mat[ni-a*di][nj-a*dj]==nv):
        a += 1
    b = 1
    while (0<=ni+b*di<19) and (0<=nj+b*dj<19) and (mat[ni+b*di][nj+b*dj]==nv):
        b += 1
    return a + b - 1

mat = [list(map(int, input().split())) for _ in range(19)]
v, i, j = main()
if v:
    print(v)
    print(i, j)
else:
    print(0)

한 달 전에 정말 코딩 접고 싶을 정도로 좌절감을 맛보여줬던 문제를 풀었다. 당시에도 완전탐색에 대한 개념은 알았지만 상하좌우 대각선의 조회를 어떻게 할지에 대한 로직의 문제를 겪었는데, 이제는 로직을 구현하는 것 자체는 어렵지 않았다.

방법은 완전탐색으로 한 칸 한 칸 조회하다가 0이 아닌 값이 있는 칸이 있다면 check() 함수를 실행하는 main() 함수를 작성하는 것이다. main() 함수를 굳이 함수로 작성한 이유는 만약 해당 칸으로부터의 조회가 오목을 이룬다면 이후 완전탐색을 멈추고 return 하면 되기 때문인데, 함수 외부에서 하게 된다면 flag 요소를 두어 매 탐색마다 체크를 하는 번거로움을 감수해야하기 때문이다.

아무튼 main() 함수는 check4() 함수 내부로 현재 위치의 값, 그리고 현재 좌표를 전달한다. 이를 이용해 check4() 함수는 현재 좌표로부터 좌우, 상하, 오른쪽 대각선, 왼쪽 대각선을 각각 조회하는데, 이를 check() 함수를 이용해 구현했다. di, dj를 지정해서 전달한다.

main() 함수는 nv, ni, nj, di, dj를 전달받아 조회를 시작하는데, 현재 좌표로부터 while문을 이용해 해당 값이면 di, dj를 하나씩 더하거나 빼주며 양 방향으로 조회를 뻗쳐나가는 것이다. check 함수를 따로따로 4개를 만들면 di, dj가 필요하지 않지만, check() 함수의 중복을 제거하기 위해 di, dj와 가중치 a, b를 이용했다.

a와 b의 합에서 1을 뺀 값이 해당 좌표에서 양쪽으로 뻗쳐나간 조회 정보이다. 이것이 4도 아니고 6도 아닌 5가 된다면 오목이므로 1을 return하고, 전체 di, dj에 대한 for문을 완료했는데도 오목이 없다면 0을 return한다.

check4() 함수에서는 check() 함수의 반환값으로부터 오목의 여부를 확인하고, 만약 check()가 True라면 오목이므로 해당 좌표와 값을 return한다.

결과

맞았습니다!!

보통 외부 i, 내부 j의 행 우선 탐색을 하는데, 이 같은 경우는 가장 왼쪽의 좌표를 출력해야하므로 열 우선 탐색을 해야하는 것이 특이했다. 이를 놓치면 틀릴 수 있었다. 실제로 나는 그것을 나중에 재확인해서 맞출 수 있었다.