글 읽기 - 파이썬>> 왜 아직 방문하지 않은 곳이 True 로 찍히는지 잘 모르겠습니다..

mickeyshoes 2년 전 0

안녕하세요 :) 이제 막 bfs, dfs 에 입문한 그린입니다..

꽤 오랜 시간 디버깅을 했는데 이유를 잘 모르겠어서.. 질문 남겨봅니다..ㅜ

bfs 를 사용해서 구현하였습니다.

문제가 되는 상황은 아직 방문하지 않은 곳이 True 로 초기화가 되어 있는 문제입니다.

문제가 되는 상황은 다음과 같습니다.

ex)

(0,1) 이 1이면서 아직 방문하지 않은 좌표이므로 방문
0,1 주위에 1이면서 방문하지 않은 좌표 찾기
1,1 이 1이면서 방문하지 않은 좌표이므로 방문
그러나 이미 True 로 아래와 같이 초기화 되어 있음( True 로 초기화는 큐에서 꺼낼때만 하고 있습니다)
1행의 방문 기록=>[False, True, False, False, False, False, False]

코린이에게 도움을 주세요.. 답변 남겨주시면 감사하겠습니다

import sys
from queue import Queue

N = int(sys.stdin.readline().rstrip('\n'))

map = []
visited = [[False]* N] * N

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

def bfs(x : int, y : int):
    q = Queue()
    q.put((x,y))
    count = 0

    while q.qsize() > 0:
        a,b = q.get()
        visited[a][b] = True
        print(f'visited {a},{b}')
        count +=1
            
        for i in range(len(dx)):
            check_x = a + dx[i]
            check_y = b + dy[i]
            if check_x < 0 or check_x >= N or check_y <0 or check_y >= N:
                print(f'filtered {i}: {check_x},{check_y}')
                continue
            elif map[check_x][check_y] == '1' and not visited[check_x][check_y]:
                q.put((check_x,check_y))
                print(f'insert queue {i} : {check_x},{check_y}')
            else:
                print(visited[check_x])
                print(f'why {i} ? : ({check_x},{check_y})\tmap : {map[check_x][check_y]} visited? : {visited[check_x][check_y]}')

    return count

for _ in range(N):
    line = list(sys.stdin.readline().rstrip('\n'))
    map.append(line)
    
for i in range(N):
    for j in range(N):
        if map[i][j] == '1' and not visited[i][j]:
            print('------------------------------------------')
            print(f'first : {i},{j}')
            print(f'** {bfs(i,j)} **')

dbshin59 2년 전 1

파이썬에서 2차원 배열을 만드는 방법이 잘못되었습니다.

visited = [[False]* N] * N 이 뜻하는 것은, 그저 요쇼를 복사하는 것을 뜻하는 것일 뿐입니다.

배열은 포인터입니다. 그런 배열을 그대로 복사하니, 포인터마저 그대로 복사합니다.

결국 여러 개의 똑같은 값을 가리키게 되어버립니다.

예를 들어, visited[0][1] 을 True로 바꾸면, visited[0]의 포인터 = visited[1]의 포인터 이기 때문에, visited[0][1] = visited[1][1] 이 되어버립니다.

제대로 된 2차원 배열을 만드는 방법은,

two_array = [[False]*N for _ in range(N)]

처럼 for문을 이용해야 합니다. (이것에 대해서는 검색을 추천드립니다.)

mickeyshoes 2년 전 0

와.. 이 점은 전혀 생각치도 못했네요.. 답변 정말 감사드립니다.

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

문제

문제

출처

ICPC

파이썬>> 왜 아직 방문하지 않은 곳이 True 로 찍히는지 잘 모르겠습니다..

mickeyshoes 2년 전 0

dbshin59 2년 전 1

mickeyshoes 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말