[ 2615 ] [ Brute-Force ] 오목

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

2615번: 오목

 

 

풀이 과정

---

1. 오목판의 왼쪽 위에서 아래쪽으로 진행하면서 전체 경우의 수를 탐색하면 된다.
   • 왼쪽 위에서 아래로 진행하므로, 위쪽 방향으로는 조사할 필요 없이 아래 방향으로만 조사하면 된다.
2. 단, 6개 이상의 돌이 연속으로 있는 경우는 안되므로 (0, 0)에서 (5, 5)까지 6개가 있는걸 (1, 1)에서부터 시작해서 (5, 5)까지 5개가 있는걸로 잘못 처리되는걸 방지하기 위해 visited 배열을 따로 둔다.
   • visited 배열의 경우는 [19][19][4] 형식으로 구성. 4는 왼쪽아래 대각, 아래, 오른쪽아래 대각, 오른쪽 총 4개의 방향으로 방문 가능하므로 3차원 배열로 구성
   • 이미 방문한 경우는 재방문하지 않도록 처리
3. 전체 경우의 수를 돌면서 오목인 경우, 해당 위치와 돌의 종류를 출력시켜주면 된다.
   • 예외사항으로, 왼쪽아래 대각 방향이 정답인 경우는 가장 왼쪽 돌을 출력해주라고 하였으므로 현재 위치 기준 x+4, y-4 해주면 된다.

---

소스 코드

---

 

import sys

input = lambda :sys.stdin.readline().rstrip()

matrix = [list(map(int, input().split())) for _ in range(19)]
visited = [[[False] * 4 for _ in range(19)] for _ in range(19)]

def check(matrix, visited, x, y):
    direction = [[1, -1], [1, 0], [0, 1], [1, 1]]
    p = matrix[x][y]

    for idx, d in enumerate(direction):
        temp_x, temp_y = x, y
        if visited[temp_x][temp_y][idx]:
            continue
        visited[temp_x][temp_y][idx] = True
        count = 1
        while True:
            temp_x, temp_y = temp_x + d[0], temp_y + d[1]
            if 0 <= temp_x and temp_x < 19 and 0 <= temp_y and temp_y < 19:
                if matrix[temp_x][temp_y] == p:
                    visited[temp_x][temp_y][idx] = True
                    count += 1
                else:
                    break
            else:
                break
            if count >= 6:
                break

        if count == 5:
            if d[0] == 1 and d[1] == -1:
                return [x+4, y-4]
            return [x, y]
        
    return None

end = False
for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] != 0:
            result = check(matrix, visited, i, j)
            if result is not None:
                i, j = result
                print(matrix[i][j])
                print(i+1, j+1)
                end = True
        if end:
            break
    if end:
        break

if not end:
    print(0)