글 읽기 - 고립된 배추들이 고려대상에조차 들어가지 않는데 어떻게 해결해야 될까요?

pp0202 1년 전 0

안녕하세요. 파이썬 bfs, dfs 개념을 쓴지 얼마 안된 초보입니다. 이번 식에서도 약간 지저분하게 쓴 감이 있다는 것은 자각하고 있는데, 그래도 고립된 배추들이 for문에 이전 식에 의해 사라질 수가 없는 구조라고 저는 해석하였습니다.

중간중간 for 문에서 print(i)를 하거나 마지막에 len(answer) 대신 answer을 넣어 결과를 도출해보았을때, 고립된 배추들은 아예 for문의 고려대상에 포함돼있지 않다는 것을 확인하였고 2개씩 붙어있는 배추들 역시 가장 먼저 고려되는 배추들은 식에서 빠져있다는 사실을 발견하였습니다. ((for i in case)문 직전에 print(case)를 하였을때는 정상적으로 모든 입력값들이 출력되었습니다.)

근데 또 5,6개씩 뭉쳐있는 배추들은 과정에서 제외되지 않고 결과값에 전부 포함되어있어 어느 부분에서 이러한 문제가 생기는 것일까 고민하다 도저히 혼자서 해결이 안되어 고수님들에게 도움을 구하고자 질문글 올렸습니다. (+추가적으로 개선할 점 있으면 그것도 얘기해주시면 감사하겠습니다!!)

import sys
input=sys.stdin.readline

T=int(input())

for _ in range(T):
    M, N, K = map(int,input().split(" "))
    case=[]

    for _ in range(K):
        test=list(map(int,input().split(" ")))
        case=case+[test]
    case.sort(key=lambda x: (x[0], x[1]))

    def bfs(a, b):
        visited = [[a, b]]
        case.remove([a, b])
        while visited:
            if [a + 1, b] in case:
                visited.append(bfs(a + 1, b))
            elif [a, b + 1] in case:
                visited.append(bfs(a, b + 1))
            else:
                break
        return visited

    answer=[]
    for i in case:
        answer.append(bfs(i[0], i[1]))
    print(len(answer))

seawon0808 1년 전 0

17번째 줄에서 case.remove를 사용하셔서 28번째 줄의 for i in case에 문제가 생기는 것 같습니다.

adung7 1년 전 0

개인적으로 이런 2차원배열에서의 bfs,dfs는 틀이 정해져있다라고 봅니다.

따라서 bfs만큼은 처음 개념을 접했을땐 혼자 고민해보는것도 좋지만 남의 코드를 보고 틀을 배우는것이 좋다고 생각해요.

블로그를 참고하시거나 혹시나 제 코드를 보고싶으시면 https://ideone.com/UuX8hm 참고해보세요.

pp0202 1년 전 0

case.remove를 하였을 때 고립된 배추들이 사라지는 이유가 궁금합니다. 한줄한줄 생각하면서 읽어보아도 고립된 배추들이 for 반복문에서 아예 빠져버릴 이유가 생각나지 않습니다. ㅠ

pp0202 1년 전 0

혼자서 bfs 코드 짜볼라다가 아무래도 좀 지저분해진 감이 있긴합니다.. ㅎㅎ 코드 감사하게 참고하도록 하겠습니다!

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

문제

문제

출처

ICPC

고립된 배추들이 고려대상에조차 들어가지 않는데 어떻게 해결해야 될까요?

pp0202 1년 전 0

seawon0808 1년 전 0

adung7 1년 전 0

pp0202 1년 전 0

pp0202 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말