[백준] 2615번: 오목 (구현, 파이썬)

📌 문제 탐색하기

 입력으로 주어진 오목 판의 상태를 확인하고, 검은색(1)이 이겼을 경우에는 1을 출력하고, 흰색(2)이 이겼을 경우에는 2를 출력한다. 아직 무승부라면 0을 출력한다. 또한 1, 2를 출력한다면, 가장 왼쪽에 있는 바둑알의 좌표를 출력해야한다. 

🔎 문제 조건

• 검은 바둑알 또는 흰색 바둑알이 5개 놓여 오목일때, 해당 색상을 출력하고, 상단 좌표를 출력해야한다.
• 가장 왼쪽에 있는 좌표를 출력해야하므로 ↙ 방향으로 오목이 생길때는 마지막으로 탐색한 좌표를 출력해야한다. 

🔎  시간 복잡도

• 19 x 19자리에서 4방향(↙,↓,↘,→ )에 대해 탐색을 진행하므로 시간 제한 1초 안에 해결할 수 있다. 

🔎 접근 방법 및 알고리즘

•  ↙, ↓, ↘, → 순서대로 DFS를 진행했다.
• 여섯 알 이상이 놓인 경우, 이긴 것이 아니므로 6개에 대한 탐색을 진행해야한다.

📌 코드 설계하기

1️⃣ 오목판 21x21 배열을 0으로 초기화한다. (좌표 편리를 위해)

2️⃣ 방향 벡터를 정의한다. (↙, ↓, ↘, →)

3️⃣ DFS: 이전 돌의 좌표가 같은 색이면 다음 좌표로 

4️⃣ 이중 FOR문으로 돌을 확인한다, 돌이 있다면 4방향으로 DFS 탐색을 진행한다. 

5️⃣ (DFS함수) 첫 돌의 이전 좌표가 같은 색이면, 재귀함수를 통해 계속 수행한다. 

6️⃣ (DFS함수) cnt == 5인 경우 정답 좌표를 ans X, ansY에 저장한다.

7️⃣ (DFS함수) cnt == 6이면 오목을 무효화한다. 

8️⃣ 탐색이 끝난 후에도 없다면 0을 출력한다. 

📌 시도 회차 수정사항

• 오목을 찾는 함수 내부에 dx, dy를 순회하는 것을 넣으면 직선이 될 수 없다. 따라서, 밖으로 빼내었다. 

📌 정답 코드 

import sys

# 오목판 21x21 생성 (1~19 사용)
omok = [[0] * 21 for _ in range(21)]
ansX, ansY = 0, 0

# 방향 벡터: ↙, ↓, ↘, →
dx = [1, 1, 1, 0]
dy = [-1, 0, 1, 1]

# DFS를 이용한 오목 체크
def dfs(x, y, value, cnt, direction):
    global ansX, ansY

    # 유효한 좌표인지 확인하는 함수
    def is_valid(tx, ty):
        return 1 <= tx <= 19 and 1 <= ty <= 19

    if cnt == 1:
        prev_x, prev_y = x - dx[direction], y - dy[direction]
        if is_valid(prev_x, prev_y) and omok[prev_x][prev_y] == value:
            return False

    tx, ty = x + dx[direction], y + dy[direction]

    if cnt == 5:
        ansX, ansY = x, y

        if not is_valid(tx, ty) or omok[tx][ty] != value:
            return True
        else:
            return False

    if is_valid(tx, ty) and omok[tx][ty] == value:
        return dfs(tx, ty, value, cnt + 1, direction)

    return False

# 오목판 입력받기
input = sys.stdin.read
data = input().split()
index = 0

for i in range(1, 20):
    for j in range(1, 20):
        omok[i][j] = int(data[index])
        index += 1

# 오목 탐색
for i in range(1, 20):
    for j in range(1, 20):
        if omok[i][j] != 0:
            for k in range(4):
                if dfs(i, j, omok[i][j], 1, k):
                    if k == 0:  # ↙ 방향일 때
                        print(omok[i][j])
                        print(ansX, ansY)
                    else:
                        print(omok[i][j])
                        print(i, j)
                    sys.exit()

print(0)