반응형 BFS32 백준 12851번 숨바꼭질 2 - 스위프트(Swift) 풀이 1697번 숨바꼭질 문제에 추가로 경우의 수까지 출력해야 하는 문제. 1. 각 점을 정점이라고 생각한다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다. 3. 정점 N에서 K까지의 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS로 쉽게 구할 수 있다. 4. BFS를 돌 때 이미 방문했던 곳이더라도 해당 정점을 N에서 최단거리로 온 경우라면, 또 방문해서 경우의 수를 카운트해준다. ↓ 1, 2, 3번에 대한 설명은 1697번 풀이를 확인 ↓ 백준 1697번 숨바꼭질 - 스위프트(Swift) 풀이 현재 상황을 그래프로 치환할 수 있음을 떠올리면 그 뒤로 구현은 쉽다. 1. 각 점을 정점이라고 생각한다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가.. 2022. 1. 15. 백준 1697번 숨바꼭질 - 스위프트(Swift) 풀이 현재 상황을 그래프로 치환할 수 있음을 떠올리면 그 뒤로 구현은 쉽다. 1. 각 점을 정점이라고 생각한다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다. 3. 정점 N에서 K까지의 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS로 쉽게 구할 수 있다. 1. 각 점을 정점이라고 생각한다. 현재 상황을 그래프로 나타낼 수 있다. 0부터 100,000번까지 총 100,001개의 정점이 있다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다. X번 정점에서 1초 만에 다이렉트로 갈 수 있는 정점은 X+1, X-1, X*2이다. 그래프에 X에서 저 세 정점으로 가는 방향 간선을 추가해준다. 방향 간선이라는 것을 주의해야 한다.. 2022. 1. 15. 이전 1 ··· 4 5 6 7 다음 반응형
