[백준] 2615 오목 (Python) - Brute Force

📌 문제

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 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

---

📌 풀이

Code

import sys
input = sys.stdin.readline

def omok(arr):
    stone = -1                   # 돌 종류
    # → ↓ ↘ ↗ (왜? 가장 왼쪽에 있는 바둑알의 좌표를 출력해야 하니까!!)
    dr = [0, 1, 1, -1]           # 행 델타
    dc = [1, 0, 1, 1]            # 열 델타
    
    for r in range(19):
        for c in range(19):
            
            if arr[r][c] == 0: continue       # 돌 없는 경우 패스
            stone = arr[r][c]                 # 현재 돌의 종류             

            for k in range(4):                # 우, 우하, 하, 좌하 탐색
                cnt = 1                       # 돌 하나는 찾은 상태니 초기값 1
                for n in range(1, 6):         # 6목 여부도 봐야하니 6까지
                    nr = r + dr[k]*n
                    nc = c + dc[k]*n
                    if 0 <= nr < 19 and 0 <= nc < 19 and arr[nr][nc] == stone:
                        cnt += 1
                    else:
                        break
                if cnt == 5:                  # 정확히 5개 연속일 때만
                    # 이전 위치에 같은 돌이 있는지 확인
                    prev_r = r - dr[k]
                    prev_c = c - dc[k]
                    if 0 <= prev_r < 19 and 0 <= prev_c < 19 and arr[prev_r][prev_c] == stone:
                        continue
                    # 이전 위치에 같은 돌이 없으면 정확히 5개 연속이라는 뜻이므로
                    return stone, (r+1, c+1)  # 해당 돌 승리 (with 가장 왼쪽 돌 좌표)
    return 0, None                            # 마지막까지 승리자 없으면 0 반환

arr = [list(map(int, input().split())) for _ in range(19)]  # 바둑판
winner, pos = omok(arr)
print(winner)
if winner:      # 승부가 결정난 경우만 출력
    print(*pos)

 

Solution

1. (0, 0) 부터 (18, 18)까지 모든 좌표 체크

 

2. 바둑알을 만나면 그 돌의 색을 기억하고, → ↓ ↘ ↗ 방향으로 6칸씩 체크

• 6칸인 이유: 5칸 이후에 같은 돌이 하나 더 나타나면 6목이 되기 때문에

3. 해당 방향으로 for문이 다 끝났을 때 카운트가 5이면 첫번째 바둑돌보다 한 칸 이전의 바둑돌 체크

• 첫번째 바둑돌보다 한 칸 이전의 바둑돌 체크하는 이유: 해당 방향으로도 6목일 수 있지만 반대 방향으로도 6목일 수 있기 때문에

 

위 그림처럼 초록색 화살표만 보면 5목이지만, 반대 방향인 보라색 화살표까지 확인하면 6목이 됩니다!!

---

깨달은 점

저는 이전에 swea 문제를 풀고 왔어서 그런지, 별 생각 없이 → ↓ ↘ ↙ 방향을 체크했습니다.

빨간색 화살표 보이시나요..? 저 녀석이 문제였습니다.

 

문제를 보면 가장 왼쪽에 있는 바둑알의 좌표를 출력하라고 나와 있는데,

이 경우, ↙ 방향을 쓰게 되면 가장 오른쪽에 있는 바둑알을 출력하게 됩니다...

 

저는 이 사실을 알게 되자마자 ↙를 ↗로 바꿨고, 문제는 바로 풀렸습니다 ㅠㅠ

2시간이나 문제와 씨름하던 중 깨닫게 된 포인트였지요...

 

깨달은 점...

문제를 잘 읽자