jyc4836   2년 전

설명드리자면,

1. 입력받은 배추들의 좌표를 전부 baechus에 넣음

2. baechus에서 하나를 꺼낸 다음, 그 배추로부터 연결되는 모든 배추의 케이스를 찾기 위해 루프를 돌림(11번 줄)

3. 2에서 뽑은 배추를 시작점으로 하여 BFS를 수행(14번 줄)

4. 2에서 뽑은 배추는 다시 볼 일이 없으므로 baechus에서 제거하고, 마찬가지로 이 배추와 인접한 것들도 BFS 수행 과정에서 baechus에서 제거

5. 인접 여부는 큐 q에서 뽑은 배추의 좌표에 drxns에 넣은 상하좌우 값을 각각 더해서 만든 배열 안에 다음 검사할 배추가 있는지로 확인(18~20번 줄)

지분 아래에 있는 예시 둘 모두 답이 잘 나오는데 제출하면 틀렸다고 나오네요. 뭔가 빠뜨린 로직이 있는 걸까요?

dldyddlwl   2년 전

아래에 반례가 있습니다. 


이유는 for문을 돌리면서 remove를 썼기 때문입니다. 아래의 예시를 보면 확실히 이해가 가실 겁니다.

remove 때문에, 원래 위치에서 요소가 삭제되면서 앞으로 밀리게 되고, 앞으로 밀리게 되더라도, 원래의 인덱스로 가기 때문에 문제가 생깁니다.


예시]

0번째 원소인 1을 출력하고 1을 삭제 ( 2가 앞으로 당겨와짐, a[0] = 2가 되어버림 )

1번째 원소인 2가 출력되어야 하는데 , 삭제된 이후의 배열에서 1번째 원소는 3이므로 3이 출력

마찬가지...

위와 같은 이유로, for문에서 제대로 걸러내지 못하더군요, 그래서 오답이 나왔습니다.


a = [1,2,3,4,5,6]

for item in a:
    print(item)
    a.remove(item)

[출력]
1
3
5

jyc4836   2년 전

헉... 이상한 데에서 실수를 했네요 감사합니다 ㅠㅠ!!!

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