https://www.acmicpc.net/problem/6087 필요한 로직 : BFS + DP [논리] 최단거리가 아닌, 배열 이동 시 방향을 변경한 최소 횟수를 구하는 문제다. 따라서 출발점에서 target지점에 도착했다고 하더라도, 이 과정에서 최소한으로 방향이 바뀌었음을 확정할 수 없어서 출발점에 도착하는 모든 사례들을 비교해봐야 한다. 이때, 너비 우선 탐색시 중복관리를 했던 패턴을 바꿔줄 필요가 있다. 한번 방문한 (r,c) 지점을 다시 방문할 수 있게 허용할 때는 vis[r][c]보다 현재 path에서 더 작거나 같은 횟수로 방향을 바꿀 수 있을 때가 된다. 즉, 중복은 최소한의 turn 수로 바꿀 수 있는 원소에 한해서만 허용한다는 의미다. 이를 위해 vis는 bool값..........
6087번 레이저 통신에 대한 요약내용입니다.
자세한 내용은 아래에 원문링크를 확인해주시기 바랍니다.
원문링크 : 6087번 레이저 통신
네이버 블로그
티스토리
커뮤니티