[Python] S1_2615_오목 ⚫⚪

https://www.acmicpc.net/problem/2615

문제

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

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

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

입력

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

출력

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

예제

조건

• 시간 제한: 1초
• 메모리 제한: 128MB

---

코드

초기 코드

import sys
input = sys.stdin.readline

def DFS(x,y,direction,cnt):

    if cnt == 5:     # 승자를 찾은 경우
        
        # 육목인지를 확인
        mx1,my1 = x+dx[direction],y+dy[direction]
        mx2,my2 = i-dx[direction],j-dy[direction]
        temp1,temp2 = True,True
        # 마지막 돌에서 육목 확인
        if 0 <= mx1 < 19 and 0 <= my1 < 19:
            if board[mx1][my1] == color:
                temp1 = False
        # 시작한 돌에서 육목 확인
        if 0 <= mx2 < 19 and 0 <= my2 < 19:
            if board[mx2][my2] == color:
                temp2 = False 
        # 앞 뒤 모두 육목이 아님을 확인한 경우
        if temp1 and temp2:
            print(color) # 승자 출력
            if direction in [1,3,5,7]: # 시작한 돌이 가장 왼쪽 돌인 경우
                print(i+1,j+1)   # 시작한 돌의 가로줄, 세로줄 출력
            else: # 마지막 돌이 가장 왼쪽 돌인 경우
                print(x+1,y+1)   # 마지막 돌의 가로줄, 세로줄 출력 
            exit(0)      # 승자를 출력 후 강제 종료
        
    nx = x + dx[direction]
    ny = y + dy[direction]
    if 0 <= nx < 19 and 0 <= ny < 19:
        if board[nx][ny] == color:
            DFS(nx,ny,direction,cnt + 1)

board = [list(map(int,input().split())) for _ in range(19)]
# 순서대로 0.상 1.하 2.좌 3.우 4.왼쪽위 5.오른쪽위 6.왼쪽아래 7.오른쪽 아래
dx = [-1,1,0,0,-1,-1,1,1]
dy = [0,0,-1,1,-1,1,-1,1]
# 모든 오목판 탐색
for i in range(19):
    for j in range(19):
        if board[i][j] == 1 or board[i][j] == 2: # 흑 or 백 인 경우
            color = board[i][j] # 돌의 색깔
            for n in range(8):  # 주변 탐색
                nx = i + dx[n]
                ny = j + dy[n]
                if 0 <= nx < 19 and 0 <= ny < 19:
                    if board[nx][ny] == color:
                        DFS(nx,ny,n,2) # n은 방향의 정보, 이미 하나를 찾았으므로 2개부터 시작
                        
print(0) # 모든 탐색을 마쳤지만 승자를 가릴 수 없는 경우(= 아무도 이기지 않은 경우)

처음에는 이런식으로 DFS를 활용했고, 8가지 모든 방향에 대해서 탐색을 진행했었다. 풀면서도 좀 비효율적인 것 같은데..?라는 생각이 들었지만 결국 정답은 맞출 수 있었다.

수정 코드

import sys
input = sys.stdin.readline

board = [list(map(int,input().split())) for _ in range(19)]
# → ↓ ↘ ↗ 방향으로 이동
dx = [0,1,1,-1]
dy = [1,0,1,1]

for x in range(19):
    for y in range(19):
        if board[x][y] != 0:
            color = board[x][y]
            
            for i in range(4):
                cnt = 1 # 연속된 같은 돌의 개수
                nx = x + dx[i]
                ny = y + dy[i]

                while 0 <= nx < 19 and 0 <= ny < 19 and board[nx][ny] == color:
                    cnt += 1
                    # 육목 체크
                    if cnt == 5:
                        # 첫번째 돌에서 하나 이전 돌을 확인
                        if 0 <= x - dx[i] < 19 and 0 <= y - dy[i] < 19 and board[**텍스트**x - dx[i]][y - dy[i]] == color:
                            break
                        # 마지막 돌에서 하나 이후 돌을 확인
                        if 0 <= nx + dx[i] < 19 and 0 <= ny + dy[i] < 19 and board[nx + dx[i]][ny + dy[i]] == color:
                            break
                        # 육목도 아님을 확인하여, 최종적으로 승부가 난 경우
                        print(color)   # 흑 or 백을 출력
                        print(x+1,y+1) # 첫번째 돌의 가로,세로줄 번호를 출력
                        exit(0)
                    
                    # 일정한 방향으로 계속 진행
                    nx += dx[i]
                    ny += dy[i]
# 승부가 나지 않은 경우
print(0)

결국 서칭을 해본 결과, 굳이 DFS로 풀 필요도 없이 브루트 포스로 풀면 되고, 4방향만 파악을 해도 된다는 것을 알게 되었다.

• 왼쪽 위부터 시작을 하기도 하고, 최종 출력을 할 때 가장 첫번째 돌의 좌표를 함께 출력해야하기 때문에, → ↓ ↘ ↗의 4방향으로 이동하는 것이 좋다.

👉 첫번째 돌의 x와 y에 1씩만을 더해서 출력해주면 되기 때문이다.

모든 board를 파악해주는데, 돌이 아닌 경우에는 넘어간다.

• 흑 or 백돌을 발견하면, color로 지정한 후에 한 방향으로 계속해서 뻗어나가며 탐색한다.

가장 중요한 점이 육목인 경우를 알아내는 것인데, 이는 같은 색의 돌이 5개가 되었을 때 알아볼 수 있다.

• 첫번째 돌에서의 하나 이전 돌과 마지막 돌에서의 하나 이후 돌을 보고 둘 중 하나라도 같은 색의 돌이 나온다면 육목이 되므로 break해준다.

최종적으로 승부가 났음을 확인하면, 색깔과 좌표를 출력해주며 종료한다.

• 여러 반복문의 안쪽에서 종료해주어야하기 때문에, exit(0)을 사용해준다.

🤗 성능이 조금은 더 좋아졌음을 볼 수 있다!

---

느낀 점 & 배운 점

1. 처음에는 방향만 잘 설정하면 쉬운 그래프 문제일 것이라고 생각했는데, 그렇지 않았다. 방향을 고정해서 푸는 문제는 이번이 처음이었어서 조금 시간이 걸렸던 것 같다.

2. 역시 가끔은 단순하게 브루트 포스로 접근하는 것도 필요한 것 같다. 그래프 탐색과 브루트 포스에 대한 시야가 더 넓어지는 좋은 문제였다고 생각한다!