[알고리즘/백준] 2615번 오목 Python 파이썬

 

이번 문제는 어려운듯 안 어려운듯 했는 문제였다.

 

 

바둑판이 주어졌을 때 흑돌이 이겼는지 백돌이 이겼는지 아직 결판이 안 났는지를 출력하고 이긴 자가 있다면 제일 왼쪽 상단 돌의 위치를 출력하는 문제이다. 푸는 데 고려한 점은 어떻게 검사해줄까 였고 주의할 점은 딱 5개만 이기고 5개 미만이거나 6개 이상 이어질 경우 이겼다고 판단하지 않는다는 점이다. 

 

다음과 같은 코드를 통해 통과하였다.

 

from collections import deque
import sys
input = sys.stdin.readline

map_pos = [list(map(int,input().split())) for _ in range(19)]

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

for i in range(19):
    for j in range(19):
        if map_pos[i][j] != 0:
            num = map_pos[i][j]
            for k in range(4):
                check = 1
                x = i + dx[k]
                y = j + dy[k]
                while 0 <= x < 19 and 0 <= y < 19 and map_pos[x][y] == num:
                    check += 1
                    if check == 5:
                        if 0 <= i - dx[k] < 19 and 0 <= j - dy[k] < 19 and map_pos[i - dx[k]][j - dy[k]] == num:
                            break
                        if 0 <= x + dx[k] < 19 and 0 <= y + dy[k] < 19 and map_pos[x + dx[k]][y + dy[k]] == num:
                            break
                        print(num)
                        print(i+1, j+1)
                        sys.exit(0)
                    x += dx[k]
                    y += dy[k]
print(0)

 

다만 처음에는 위 방법이 아닌 큐를 이용한 BSF 알고리즘을 이용하여 풀려고 하였는데 틀렸다고 떳다. 예제로 주어진 것은 맞았는데 어느 부분이 안되었는지 모르겠다. 또 고민인 점은 왼쪽 제일 상단에서 검사해주는 만큼 오목이 되었을 때 육목이 되는지 끝 부분의 다음 부분을 검사하는 것은 이해했으나 처음의 전 돌을 검사해주는 부분을 잘 모르겠다. 처음의 전 돌이 있었다면 아 이제 이해했다. 육목일경우 따로 체크한 돌인지 아닌지 표시를 안해준다면 육목 두번째 돌을 처음으로 검사하면 전돌을 검사하지 않는 이상 오목이라고 판단할 수도 있다. 그래서 전 돌도 검사해주는 것 같다. 

 

아래는 오류난 코드임으로 참고하지 않았으면 한다. 후에 고칠려고 남겨둔 코드이다.

 

from collections import deque
import sys
input = sys.stdin.readline

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

check_pos_x = [1,0, 1, -1]
check_pos_y = [0,1, 1, 1]

check_finish = 0
for i in range(19):
    for j in range(19):
        if map_pos[i][j] != 0 and visited[i][j] == False:
            num = map_pos[i][j]
            visited[i][j] = True
            for k in range(4):
                nx = i + check_pos_x[k]
                ny = j + check_pos_y[k]
                queue = deque([])
                queue.append([nx,ny])
                check = 1
                while queue:
                    x, y = queue.popleft()
                    if 0 <= x < 19 and 0 <= y < 19 and map_pos[x][y] == num and visited[x][y] == False:
                        check += 1
                        visited[x][y] = True
                        nx = x + check_pos_x[k]
                        ny = y + check_pos_y[k]
                        queue.append([nx, ny])
                if check == 5:
                    check_finish = num
                    first_x = i
                    first_y = j
print(check_finish)
if check_finish != 0:
    print(first_x+1, first_y+1)

 

밤이라 머리가 안 돌아간다 나중에 다시 보고 고쳐야겠다.