[알고리즘] 백준 파이썬 2615 오목

📍 문제 탐색하기

오목 문제는 19×19 바둑판에서 가로, 세로, 대각선 방향으로 같은 색의 바둑알이 정확히 5개 연속된 경우 승리를 판별하는 문제이다. 주어진 바둑판 상태에서 검은 돌(1) 또는 흰 돌(2)이 이겼는지 판단하고, 승리한 경우 해당 돌의 시작 좌표를 출력한다.

---

문제 조건

• 승리 조건:
  • 같은 색의 바둑알이 정확히 5개 연속된 경우.
  • 6개 이상 연속되면 승리가 아님.
• 출력:
  • 승리한 돌의 색상(1 또는 2)과 가장 왼쪽/위쪽의 바둑알 좌표(1-based).
• 패배 조건:
  • 승부가 결정되지 않으면 0 출력.

---

입력 범위

1. 바둑판 크기: 19×19
2. 돌의 값:
   • 1: 검은색 돌
   • 2: 흰색 돌
   • 0: 빈 칸

---

가능한 시간 복잡도

1. 모든 칸(19×19)을 탐색하면서 4방향에 대해 확인:
   • O(361×4) = 약 1,444 연산.

---

📍 코드 설계하기

1. 방향 탐색 정의

• 4방향으로 연속된 바둑알 탐색:
  • 가로: 오른쪽 (0, 1)
  • 세로: 아래쪽 (1, 0)
  • 우하향 대각선: (1, 1)
  • 우상향 대각선: (-1, 1)

2. 탐색 로직

1. 바둑판의 모든 칸 탐색:
   • 돌이 있는 칸에서만 탐색 시작.
2. 중복 방지:
   • 이전 칸이 같은 색이면 이미 확인된 연속성으로 간주하고 건너뜀.
3. 정확히 5개 확인:
   • 탐색 방향의 끝에서 양쪽 끝을 확인해 여섯 개 이상인지 판별.

---

📍 시도 회차 및 수정 사항

1차 시도 (문제 해결) ✅

import sys
input = sys.stdin.readline

g = [list(map(int, input().split())) for _ in range(19)]

directions = [(0,1), (1,0), (1,1), (-1,1)]

def isValid(nx, ny):
    return 0 <= nx < 19 and 0 <= ny < 19

def dfs(x,y,color,direction,count):
    nx = x + direction[0]
    ny = y + direction[1]

    if isValid(nx, ny) and g[nx][ny] == color:  
        return dfs(nx,ny,color,direction,count+1)
    return count

for i in range(19):
    for j in range(19):
        if g[i][j] == 1 or g[i][j] == 2:
            for direction in directions:
                if dfs(i,j,g[i][j],direction,1) == 5:
                    px, py = i - direction[0], j - direction[1]
                    if isValid(px, py) and g[px][py] == g[i][j]:
                        continue
                    print(g[i][j])
                    print(i + 1, j + 1)  
                    sys.exit(0)  

print(0)