ndb796
bfs.실전문제_미로 탈출
안녕하세요. 알고리즘 공부하는 도중 궁금한 점이있어 질문드립니다. 왕초보라 질문 수준이 낮아도 이해 부탁드립니다.
마지막 코드에서 print(bfs(0,0)) 이부분이 이해가 안가는데, 시작점이 (1,1)인데 왜 (0,0)이라 쓰신건가요??? (0,0)이 무엇을 의미하는지 궁금합니다!
안녕하세요. 저도 문제를 다시 읽어봤는데 초기 위치가 (1, 1)이라고 명시되어 있어서 살짝 헷갈릴 수도 있겠네요. 다만, (0,0)으로 쓴 이유는 코드의 가독성과 관습이라고 보는데요, 예를 들면 리스트에서 "첫번째" 원소는 list[1]이 아니라 list[0]인 것과 같이, 이 문제에서 graph의 첫번째 원소(시작위치)는 graph[1][1]이 아니라 graph[0][0]입니다.
bfs(x, y)함수 구현부분을 보시면 x와 y는 내용상 graph의 인덱스로 쓰이기 때문에, 만약 bfs(1, 1)로 호출하려면 함수 구현 시 x, y 대신에 x - 1, y - 1로 작성해야 한다는 불편함이 있습니다.
만약 호출도 bfs(1, 1)로 하고 함수 구현도 x, y를 그대로 쓰고 싶다면.. 또 다른 방법으로 (N+1)*(M+1) 크기의 graph에, 첫번째 행과 열을 건너뛰고 [1]-[N]번 행과 [1]-[M]번 열에 입력을 각각 넣는 것인데, 이는 아시다싶이 여러모로 낭비스럽습니다.
(참고로 DFS(5-8), BFS(5-9) 구현 코드에서는 visited = [False] * 9와 dfs(graph, 1, visited)와 같이 작성했지만 여기서는 1차원 배열이라 낭비가 덜하기도 하고, 이론에 더 집중하기 위한 의도 같습니다. 구분해서 보시길 바랍니다.)
안녕하세요. 저도 문제를 다시 읽어봤는데 초기 위치가 (1, 1)이라고 명시되어 있어서 살짝 헷갈릴 수도 있겠네요. 다만, (0,0)으로 쓴 이유는 코드의 가독성과 관습이라고 보는데요, 예를 들면 리스트에서 "첫번째" 원소는
list[1]이 아니라list[0]인 것과 같이, 이 문제에서 graph의 첫번째 원소(시작위치)는graph[1][1]이 아니라graph[0][0]입니다.
bfs(x, y)함수 구현부분을 보시면 x와 y는 내용상 graph의 인덱스로 쓰이기 때문에, 만약bfs(1, 1)로 호출하려면 함수 구현 시x,y대신에x - 1,y - 1로 작성해야 한다는 불편함이 있습니다.만약 호출도
bfs(1, 1)로 하고 함수 구현도x,y를 그대로 쓰고 싶다면.. 또 다른 방법으로 (N+1)*(M+1) 크기의 graph에, 첫번째 행과 열을 건너뛰고 [1]-[N]번 행과 [1]-[M]번 열에 입력을 각각 넣는 것인데, 이는 아시다싶이 여러모로 낭비스럽습니다. (참고로 DFS(5-8), BFS(5-9) 구현 코드에서는visited = [False] * 9와dfs(graph, 1, visited)와 같이 작성했지만 여기서는 1차원 배열이라 낭비가 덜하기도 하고, 이론에 더 집중하기 위한 의도 같습니다. 구분해서 보시길 바랍니다.)
이해했습니다ㅎ 좋은 답글 달아주셔서 정말 감사합니다:)