[2615] 오목 (Python)

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

2615번: 오목

---

문제

오목 문제를 요약하면 다음과 같다.

 

• 가로, 세로 19줄씩 있는 바둑판
• 같은 색의 바둑알이 연속으로 5알이 놓이면 이김 - 가로, 세로, 대각선
• 6알 이상 연속적으로 놓이면 이긴 것이 아님
• 검은 바둑알 1, 흰 바둑알 2, 알이 놓이지 않는 자리는 0
• 바둑판 상태가 주어졌을 때, 검은색과 흰색 중 누가 이겼는지 or 비겼는지 판단하는 프로그램

 

 

풀이

먼저 모든 2차원 바둑알의 위치를 위부터 아래까지, 왼쪽부터 오른쪽까지 순서대로 보면서 검은알과 흰알이 있는지를 찾아보았다. 검은알이나 흰알이 있다면 처음에 이동할 방향을 찾도록 하였다.

찾을 수 있는 방향은 상하좌우와 대각선 방향까지 총 8개가 있다. 하지만 왔던 방향으로 다시 돌아가거나 이미 탐색한 방향을 중복하여 탐색하지 않기 위해 ⬇️ ↘️  ➡️ ↗️ 4가지 방향으로만 찾아보도록 하였다.

 

처음 이동할 방향을 찾았다면 같은 방향으로만 탐색하는 함수인 search함수를 수행하도록 하였다.

이 때, 파라미터로 들어온 방향의 반대 방향에 같은 값이 없는 경우만 탐색을 진행한다.

이는 아래와 같은 상황을 피하기 위해서다.

1번에서 ↘️ 방향으로 탐색을 하면 6개의 검은알이 존재해 이긴 것이 아니지만 2번에서 탐색하면 5개의 검은알로 이긴 것이 된다. 이러한 상황을 피하기 위해 탐색할 방향의 반대방향에 같은 값이 있다면 함수를 중지하도록 하였다.

 

이후 같은 색 알을 탐색하여 개수를 찾아 어느 색 알이 이겼는지 또는 비겼는지를 판단하면 된다.

 

 

코드

구현 방식은 다음과 같다.

 

1. 검은알이나 흰알이 있는 위치를 탐색

2. 다음 4가지 방향 ⬇️ ↘️  ➡️ ↗️ 에 같은 색의 알이 존재하는지 확인

3. 같은 색의 알이 존재한다면 search 함수 수행

4. search 함수에서 특정 방향으로 계속 탐색하며 이전 방향에 값이 있다면 탐색을 중지

 

import sys

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


dx=[1,1,0,-1]   # 반시계방향
dy=[0,1,1,1]
# 같은 방향으로만 탐색하는 함수(매번 주위 탐색해서 값이 있다면 다시 양수로 바꾸기)
def search(graph,x,y,color,dir):
    # count
    count = 1
    # 이전 방향에 같은 값이 있을 때
    nx = x - dx[dir]
    ny = y - dy[dir]
    if nx>=0 and nx<19 and ny>=0 and ny<19 and graph[nx][ny] == color:
        return 0
    # 이전 방향에 같은 값 없을 때
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]
        if nx<0 or nx>=19 or ny<0 or ny>=19:
            return count
        if graph[nx][ny] == color:
            count += 1
            x = nx
            y = ny
            continue
        return count

# main 코드
count = -1
for j in range(19):
    for i in range(19):
        if graph[i][j] == 1 or graph[i][j] == 2:
            # 처음 방향 찾기(가능한 모든 방향으로 이동)
            for k in range(4):
                ni=i+dx[k]
                nj=j+dy[k]
                if ni<0 or ni>=19 or nj<0 or nj>=19:
                    continue
                if graph[ni][nj] == abs(graph[i][j]):
                    count = search(graph,i,j,graph[i][j],k)   # graph,x,y,color,dir
                if count == 5:
                    print(abs(graph[i][j]))
                    print(i+1,j+1)
                    break
            if count == 5: break
    if count == 5: break

if count != 5:
    print(0)

 

 

 

사실 어째저째 문제를 해결하기는 했지만 코드가 깔끔하지 않은 것 같다. 시간 나면 코드를 다시 수정해봐야겠다.