44851

• 

  백준 - 4485 녹색 옷 입은 애가 젤다지? 풀이 방법 오랜만에 도전한 골드 문제!! 처음에 생각없이 BFS 로 코드를 짰는데 메모리 초과가 발생해서 방향을 다시 잡고 코드를 치기 시작했다. 이 문제의 핵심 포인트는 녹색옷을 입을 애가 젤다라는 점!! 이 아니고ㅋㅋㅋㅋ 2차원 배열로 입력받는다고 하더라도 결국 n-1, n-1 좌표에 도착하는 최소값을 구하는 문제라는 점이다. BFS 나 DFS 로 푸는것이 아니라 다익스트라 알고리즘을 사용해야한다. 다만 우리는 그래프 형식이 아니고 배열로 입력받기 때문에 어떻게 좌표(노드)에서 좌표(노드) 로 넘어갈 수 있는지 고민해야한다. 나는 이 부분을 DFS, BFS 에서 사용하던 dx, dy 배열을 사용해서 풀이를 하였다. 즉, dx, dy 를 통해 계산된 nx, ny 좌표가 배열의 범위 안에 존재하면 이전 .. Java - 알고리즘 2022. 9. 2.