[BOJ] 오목


  • BOJ의 오목 문제 풀이입니다

문제 풀이

  • 오목 결과로 바둑알의 색깔과 가장 왼쪽에 있는 바둑알을 출력하는 문제입니다

  • 반복문을 통해 왼쪽 상단 부터 확인하면서 연속되는 5개의 숫자가 있는지 확인하기 때문에 총 4가지의 경우, 대각선 오른쪽 아래, 오른쪽, 아래, 대각선 왼쪽 아래의 경우를 확인해줍니다.

  • 예를들어 대각선 오른쪽 아래를 확인하는 아래함수를 통해, 재귀적으로 stack에 연속되는 모든 숫자의 위치를 넣어 주고 이를 반환해줍니다

  • 그리고 만약 반환된 스택에 5개가 넘는 숫자가 있는 경우에는 check_lst라는 리스트에 넣어주고, 다음 반복문에서 반환된 스택에 있는 위치 요소가 check_lst2개 이상 포함되는지 확인해줍니다

  • 만약 가장 왼쪽에 있는 숫자가 (1,1)이고 대각선 오른쪽 아래로 내려갔을 때 6개의 숫자가 연속적이라면 이는 답이 되지 않지만, 다음 반복문에서는 (2,2)부터 시작했을 때는 연속적인 숫자가 5개가 되어 정답으로 확인될 수 있기 때문입니다

  • 같은 색깔의 바둑돌 사이에 1개는 교차하는 경우 때문에 겹칠 수 있지만 2개 이상 겹치는 경우는 이전의 5개 넘게 연속되는 바둑돌안에 포함되는 경우이기 때문에, 이 때는 False를 반환해줍니다

# 길이가 5를 넘는지 확인하는 함수
def len_check(arr, check_lst):
    for i in range(len(check_lst)):
        count = 0
        for item in arr:
            if item in check_lst[i]:
                count+=1
            if count > 1:
                return False

    return True

for r in range(R):
    for c in range(C):
        if mat[r][c] != 0:
            stack = []
            stack.append([r, c])
            result = down_right(r, c, mat[r][c], stack) # 대각선 오른쪽 아래를 확인하는 함수

            # 만약 길이가 5가 넘는 경우
            if result and len(result) > 5:
                check_lst.append(result)
            elif result and len(result) == 5 and result and len_check(result, check_lst):
                result = order(result)
                print(mat[r][c])
                print(result[0][0]+1, result[0][1]+1)
                sys.exit()

전체 코드


import sys

R = 19
C = 19
mat = []


# 대각선 오른쪽 아래를 확인하는 함수
def down_right(r, c, num, stack):
    if r+1<R and c+1<C and mat[r+1][c+1] == num:
        stack.append([r+1, c+1])
        down_right(r+1, c+1, num, stack)
    return stack

# 오른쪽을 확인하는 함수
def right(r, c, num, stack):
    if c+1<C and mat[r][c+1] == num:
        stack.append([r, c+1])
        right(r, c+1, num, stack)
    return stack

# 아래를 확인하는 함수
def down(r, c, num, stack):
    if r+1<R and mat[r+1][c] == num:
        stack.append([r+1, c])
        down(r+1, c, num, stack)
    return stack

# 대각선 왼쪽 아래를 확인하는 함수
def down_left(r, c, num, stack):
    if r+1<R and c-1>=0 and mat[r+1][c-1] == num:
        stack.append([r+1, c-1])
        down_left(r+1, c-1, num, stack)
    return stack


# 가장 왼쪽에 있는 바둑알의 위치를 찾기 위한 함수
def order(arr):
    arr_sorted = sorted(arr, key = lambda x:(x[1], x[0]))
    return arr_sorted

# 길이가 5를 넘는지 확인하는 함수
def len_check(arr, check_lst):
    for i in range(len(check_lst)):
        count = 0
        for item in arr:
            if item in check_lst[i]:
                count+=1
            if count > 1:
                return False

    return True


for _ in range(R):
    mat.append(list(map(int, sys.stdin.readline().split())))

check_lst = []

for r in range(R):
    for c in range(C):
        if mat[r][c] != 0:
            stack = []
            stack.append([r, c])
            result = down_right(r, c, mat[r][c], stack)
            if result and len(result) > 5:
                check_lst.append(result)
            elif result and len(result) == 5 and result and len_check(result, check_lst):
                result = order(result)
                print(mat[r][c])
                print(result[0][0]+1, result[0][1]+1)
                sys.exit()

for r in range(R):
    for c in range(C):
        if mat[r][c] != 0:
            stack = []
            stack.append([r, c])
            result = right(r, c, mat[r][c], stack)
            if result and len(result) > 5:
                check_lst.append(result)
            elif result and len(result) == 5 and result and len_check(result, check_lst):
                result = order(result)
                print(mat[r][c])
                print(result[0][0]+1, result[0][1]+1)
                sys.exit()

for r in range(R):
    for c in range(C):
        if mat[r][c] != 0:
            stack = []
            stack.append([r, c])
            result = down(r, c, mat[r][c], stack)
            if result and len(result) > 5:
                check_lst.append(result)
            elif result and len(result) == 5 and result and len_check(result, check_lst):
                result = order(result)
                print(mat[r][c])
                print(result[0][0]+1, result[0][1]+1)
                sys.exit()

for r in range(R):
    for c in range(C):
        if mat[r][c] != 0:
            stack = []
            stack.append([r, c])
            result = down_left(r, c, mat[r][c], stack)
            if result and len(result) > 5:
                check_lst.append(result)
            elif result and len(result) == 5 and result and len_check(result, check_lst):
                result = order(result)
                print(mat[r][c])
                print(result[0][0]+1, result[0][1]+1)
                sys.exit()

print(0)



Reference









© 2020. by dkmqflx

Powered by dkmqflx