[BOJ] 2615번 - 오목

문제

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

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.

입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

입력

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

출력

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

🚦 문제 유형

• 완전 탐색

 

✏️ Solution

2차원 배열(바둑판)에서 오목을 찾으려면 한 바둑알을 기준으로 상하좌우, 대각선 방향을 살펴봐야 한다. 

컴퓨터가 바둑판 속의 모든 바둑알을 체크하기위해서 2차원 배열을 Linear하게 탐색하는 동안 현재 보고 있는 바둑알이 오목의 조건에 해당하는지 체크하면 된다. 그래서 이 문제는 완전탐색 유형이다.

[한 바둑알을 기준으로 오목이 만족하는지 체크하는 방법]

사람의 눈으로는 바둑판 그림 상으로 상하좌우, 모든 대각선 방향을 한번에 볼 수 있어 오목을 쉽게 찾을 수 있지만 컴퓨터는 코드의 흐름대로 바둑알을 체크하게 되므로 모든 방향을 살펴보지 않아도 된다. 즉 오른쪽아래 방향으로 바둑판을 탐색한다면, 4가지 방향만 고려해도 되는 것이다. 아래 그림에서 회색 화살표를 고려하지 않아도 되는 이유는 바둑판을 탐색하면서 이미 노란색 화살표로 커버 되는 부분이기 때문이다.

따라서 바둑알이 오목인지 체크하는 방향은 4가지가 된다. 4가지 방향을 바둑알에 각각 더해서 나온 이동한 좌표의 바둑알이 그 전 바둑알의 색과 동일한지 확인하면 되는 것이다.

• 오른쪽 위 대각선 방향 (x축 -1, y축 +1)
• 오른쪽 방향 (x축 +0, y축 +1)
• 오른쪽 아래 대각선 방향 (x축 +1, y축 +1)
• 아래 방향 (x축 +1, y축 +0)

 

[바둑알이 오목인지 체크하는 함수: Check]

1. 한 바둑알을 기준으로 4가지 방향을 순차적으로 탐색한다.
2. 이동한 좌표를 구하고 오목이 되는 조건을 확인할 수 있는 개수를 확인한다. (cnt = 1)
3. 이동한 좌표의 범위가 바둑판을 넘는지 확인하고 그 전의 바둑알의 색과 같은지 확인한다.
   1. 색이 같다면, 오목 카운트 개수를 증가(cnt += 1)하고 다음 이동좌표를 구한다.
   2. 같지 않다면, 4가지 방향 중 그 다음 방향으로 처음부터 다시 검사
4. 중간에 cnt == 5가 되면 오목이 되었으므로 최종 오목이 되기 위한 조건을 확인한다.
   1. 6목을 방지하기 위해 오목 양쪽 끝에 같은 색의 바둑알이 있는지 확인한다.
5. 최종 오목이 된 것을 확인하면, 바둑알의 번호와 좌표를 출력하고 exit(0)을 호출해 코드를 종료한다.

 

이 Check 함수를 이중 for문으로 바둑알을 탐색하면서 호출하면 된다.

import sys

# 바둑판 초기화
matrix = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(19)]

# (x, y) 현재 위치에서 오른쪽 위, 오른쪽, 오른쪽 아래, 아래 방향 
dir = [(-1, 1), (0, 1), (1, 1), (1, 0)]

def check(i, j):
    for d in dir:
        # 이동한 방향 좌표 구하기
        x, y = i + d[0], j+d[1]
        cnt = 1
        # 이동한 좌표의 범위 확인, 이동 전 좌표 == 이동 후 좌표 인지?
        while 0 <= x < 19 and y < 19 and matrix[x][y] == matrix[i][j]:
            cnt += 1
            x += d[0]
            y += d[1]
            if cnt == 5:
                # 오목이 완성 된 후 양쪽 끝에 같은 색의 바둑알이 있는지 확인 -> 6개 이상이 되는 것을 방지
                if not (0 <= x < 19 and y < 19 and matrix[x][y] == matrix[i][j]):
                    if not (0 <= i-d[0] < 19 and 0 <= j-d[1] < 19 and matrix[i-d[0]][j-d[1]] == matrix[i][j]):
                        print(matrix[i][j]) #이긴 바둑알의 번호를 출력
                        print(i+1, j+1)
                        exit(0)
                    else:
                        break
                else:
                    break

for i in range(19):
    for j in range(19):
        if matrix[i][j] != 0:
            check(i, j)

# check 함수에서 승부를 결정하지 않았을 경우 0을 출력함.
print(0)

 

 

⚙️ Review

처음 문제 풀이의 접근은 모범답안과 동일했다.

모든 바둑알의 방향을 확인해서 오목인지 확인하고 오목이면 출력하는 방향으로 코드를 짰지만 몇 가지 놓친 점이 있었다.

첫번째, 6목을 확인하지 않았다.

두번째, 바둑판의 범위를 확인하지 않았다.

 

이렇게 좌표를 사용해 푸는 문제는 (dx, dy) 배열을 만드는데 저번에도 비슷한 문제를 풀었지만 생각해내지 못했다.

다음엔 꼭 생각해내야겠다.