99클럽 코테 스터디 14일차 TIL Boj 2615. 오목

Approach

• 알고리즘 자체는 어렵지 않은 완전 탐색 문제이다
• 약 30분정도 걸렸는데, 세부 조건들을 조금 더 자세히 읽었다면 더 빠르게 풀지 않았을까 싶다….
• count로 5목인지 세면서 count == 5를 했었는데, 이렇게 되면 완전 탐색이기 때문에 아래쪽 탐색 중 count가 5여도, 반대방향에서 같은 돌이 더 있을 수도 있기 때문에 이 조건 때문에 조금 애를 먹었다.

---

Solution 💡

import sys

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

mp = [list(map(int, sys.stdin.readline().split())) for _ in range(19)]

dx = [0, 1, 1, -1]
dy = [1, 0, 1, 1]

answer = []
winner = 0

for i in range(19):
    for j in range(19):
        if mp[i][j] != 0:  
            stone = mp[i][j]

            for k in range(4):
                count = 1
                temp = [(i, j)]

                nx, ny = i + dx[k], j + dy[k]

                while is_valid(nx, ny) and mp[nx][ny] == stone:
                    temp.append((nx, ny))
                    count += 1
                    nx += dx[k]
                    ny += dy[k]

                prev_x, prev_y = i - dx[k], j - dy[k]
                if count == 5 and not (is_valid(prev_x, prev_y) and mp[prev_x][prev_y] == stone):
                    winner = stone
                    answer = temp
                    break

if winner:
    print(winner)
    answer.sort(key=lambda x: (x[1], x[0]))
    print(answer[0][0] + 1, answer[0][1] + 1)
else:
    print(0)