6087번 - 레이저 통신
BFS 로 탐색을 진행할때, 현재 정점에서 4방향의 벽이 아닌 모든 정점은 같은 Depth 에 속하기 때문에
BFS 의 Depth 를 거울의 개수로 생각 하고 진행 하였습니다. (Depth 값은 dist[][] 2차원 배열에 저장)
아래의 코드는 이미 방문을 하였더라도 dist 의 값이 더 작은 값으로 갱신될 수 있다면(탐색하려는 방향의 순서에 상관없이 dist를 갱신하기 위하여, 47번째line)
재방문을 허용하여 AC를 받은 코드입니다. (재방문을 허용하기 때문에 BFS는 아니지만... )
이렇게 작성한 코드가
dist[100][100][4] 와 같은 배열을 이용하여 4방향의 모든 방향을 고려하여 BFS를 진행후 (재방문을 허용하지 않는)
도착점에서의 dist 4가지 값중 최소값을 구하는 코드와 논리적으로 같은 결과를 도출하는지 궁금합니다..
댓글을 작성하려면 로그인해야 합니다.
7slidemorning 3년 전
BFS 로 탐색을 진행할때, 현재 정점에서 4방향의 벽이 아닌 모든 정점은 같은 Depth 에 속하기 때문에
BFS 의 Depth 를 거울의 개수로 생각 하고 진행 하였습니다. (Depth 값은 dist[][] 2차원 배열에 저장)
아래의 코드는 이미 방문을 하였더라도 dist 의 값이 더 작은 값으로 갱신될 수 있다면(탐색하려는 방향의 순서에 상관없이 dist를 갱신하기 위하여, 47번째line)
재방문을 허용하여 AC를 받은 코드입니다. (재방문을 허용하기 때문에 BFS는 아니지만... )
이렇게 작성한 코드가
dist[100][100][4] 와 같은 배열을 이용하여 4방향의 모든 방향을 고려하여 BFS를 진행후 (재방문을 허용하지 않는)
도착점에서의 dist 4가지 값중 최소값을 구하는 코드와 논리적으로 같은 결과를 도출하는지 궁금합니다..