글 읽기 - 안녕하세요 양배추 문제 관련 질문입니다.

wooooooogi 3년 전 1

안녕하세요.

매번 질문만 올리게 되네요.

제가 사용한 방법은, 먼저 arr과 arrb 리스트에 양배추가 있는 곳을 각각 1, True로 설정했습니다.

그리고 이차원 배열을 탐색하며, 그 지점에 양배추가 있다면(+arr이 1일 때) 해당 지점과 상하좌우를 탐색합니다.

그리고 5개 지점 중 가장 큰 값을 t에 할당합니다.

만약 t가 1이라면, 해당 지점은 아직 벌레를 사용하지 않은 지점이기에 벌레 값인 res를 1 증가시켜 줍니다. 그리고 t값을 1이 아닌 다른 값으로 설정해줍니다. 이 때 만약 상하좌우에 1인 값이 있다면, 이 값도 똑같이 t로 설정해줍니다.

이렇게 모든 배열을 탐색하면 필요한 벌레의 수가 나오게 됩니다.

제가 손으로 그린 경우, 문제 예제 입력은 모두 만족했으나 코드에 오류가 있어 틀렸다고 나오는 거 같습니다.

혹시 반례나, 코드 오류를 알려주실 수 있나요? 감사합니다.

import sys
for T in range(int(sys.stdin.readline())):
    M, N, K= map(int, sys.stdin.readline().split())
    arr = [[0 for i in range(M + 2)] for j in range(N + 2)]
    arrb = [[False for i in range(M + 2)] for j in range(N + 2)]
    for i in range(K):
        tarr = list(map(int, sys.stdin.readline().split()))
        arr[tarr[1] + 1][tarr[0] + 1] = 1
        arrb[tarr[1] + 1][tarr[0] + 1] = True
    res = 0
    for j in range(1, M + 1):
        for i in range(1, N + 1):
            if arrb[i][j] == True and arr[i][j] == 1:
                a0 = arr[i][j]
                a1 = arr[i - 1][j]
                a2 = arr[i][j + 1]
                a3 = arr[i + 1][j]
                a4 = arr[i][j - 1]
                t = max(a1, a2, a3, a4, a0)
                if t == 1:
                    t = 2 + res
                    res += 1 
                if arr[i][j] == 1:
                    arr[i][j] = t
                if arr[i - 1][j] == 1:
                    arr[i - 1][j] = t
                if arr[i][j + 1] == 1:
                    arr[i][j + 1] = t
                if arr[i + 1][j] == 1:
                    arr[i + 1][j] = t
                if arr[i][j - 1] == 1:
                    arr[i][j - 1] = t
    print(res)

plan222 3년 전 1

반례는 U자 모양 입니다.

단순히 상하좌우 살펴보고 끝이나면 연결된 구간을 모두 탐색 할 수 없습니다.

DFS, BFS에 대해 검색해서 알아보세요.

wooooooogi 3년 전 0

답변 감사합니다.

U자에 대한 예외코드를 작성해봤으나 U가 2개 이상 겹쳐있을 때 또 작동하지 않아 스파게티 코드가 되어 그냥 탐색 알고리즘으로 작성하도록 하겠습니다. 감사합니다 ㅎㅎ

많은 도움이 되었습니다.

for j in range(1, M + 1):
    for i in range(1, N + 1):
        if arr[i][j] > 1 and ((arr[i - 1][j] > 1 and arr[i][j] != arr[i - 1][j]) or (arr[i][j - 1] > 1 and arr[i][j] != arr[i][j - 1])):
            res -= 1
# 예외처리 하려다 실패한 코드.

댓글을 작성하려면 로그인해야 합니다.