[baekjoon] 백준 2615번(파이썬): 오목

문제

2615번: 오목

알고리즘

- 반복문을 통해 바둑알이 있는 위치를 탐색한다.

- 우/ 아래/ 대각선 우 우 아래/ 대각선 우 위 => 4가지 방향으로 탐색한다.

- 위에서부터 오른쪽으로 탐색하기 때문에 왼/위/아래 왼 아래/ 아래 왼 위 방향은 탐색할 필요 없다.

- 4가지 방향으로 탐색하면서 오목이 되는지 확인한다.

- 오목이 되는지 확인하는 방법으로는 이전에 이동했던 방향으로 5번 이동했을 때 매번 같은 바둑알의 색인지 확인하는 것이다.

- 이때 시작 점의 뒷 방향에 바둑알의 색과 끝 점의 앞 방향에 바둑알의 색이 현재 바둑알의 색과 같은지 확인하여 육목을 확인한다.

- 육목이 아니라면 오목이므로 바둑알의 색과 위치를 출력 후 출력한다.

- 탐색이 모두 끝난 후에도 시스템이 종료되지 않았으면 오목을 찾지 못한 것으로 0을 출력한다. 

코드

import sys


def bfs(x, y):
    target = graph[x][y] # 바둑알의 색

    # 우/아래/대각선 우 아래/ 대각선 우 위 => 4가지 방향을 탐색
    for k in range(4):
        cnt = 1 # 바둑알 수
        nx = x + dx[k]
        ny = y + dy[k]

        # 반복문을 통해 오목이 되는지 확인
        while 0 <= nx < 19 and 0 <= ny < 19 and graph[nx][ny] == target:
            cnt += 1

            # 오목이라면
            if cnt == 5:
                # 육목 체크
                if 0 <= x - dx[k] < 19 and 0 <= y - dy[k] < 19 and graph[x - dx[k]][y - dy[k]] == target:
                    break
                if 0 <= nx + dx[k] < 19 and 0 <= ny + dy[k] < 19 and graph[nx + dx[k]][ny + dy[k]] == target:
                    break

                # 육목이 아니면 성공한 것으로
                # 바둑알의 색과 위치를 출력 후 종료
                print(target)
                print(x + 1, y + 1)
                exit(0)

            # 이전에 이동했던 방향으로 다시 이동
            nx += dx[k]
            ny += dy[k]


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

# → ↓ ↘ ↗
dx = [0, 1, 1, -1]
dy = [1, 0, 1, 1]

# 반복문을 통해 바둑알이 있는 위치를 탐색
for i in range(19):
    for j in range(19):
        if graph[i][j] != 0:
            bfs(i, j)

print(0)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법