BFS
-
[프로그래머스] 게임 맵 최단거리알고리즘/프로그래머스 2021. 7. 21. 14:46
문제 링크 풀이법 큐를 이용해서 풀 수 있습니다. 이 문제는 깊이 우선이 아니라 너비 우선 방식으로 풀어야 합니다. 너비 우선 방식을 이용하면 모든 노드에 도달하는 카운트가 최소가 됩니다. 현재 노드에서 동서남북 방향을 훑어 보고 처음 방문한 곳이면서 노드 값이 1인 경우에 탐색을 합니다. 이 과정이 순차적으로 이루어지며, 탐색을 선점하게 되면 해당 위치의 카운트는 갱신되지 않게 코드를 작성할 것이기 때문입니다. 프로그래머스에선 이차원 배열을 vector로 선언했을 때 속도가 더 빠르게 나오는 걸 확인했습니다. 하지만 효율성 테스트와 비주얼 스튜디오 2019에선 당연히 정적으로 선언한 경우가 더 빨랐습니다. 예제 1번 기준으로는 0.2ms 차이가 났고, 효율성 테스트에서는 0.05~0.07ms로 작은 차..
-
[프로그래머스] 네트워크(DFS/BFS)알고리즘/프로그래머스 2019. 8. 23. 13:30
문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][..