BFS

[프로그래머스] Lv.3 가장 먼 노드 (BFS) + 시간초과, 메모리초과 해결

가장 먼 노드 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1번 node 에서 모든 node 로 가는 길이를 구한다. 이 때 모든 edge 의 가중치는 1이다. 즉 1 > 2 = 1 , 1 > 2 >5 = 3 , 1 > 3 > 6 = 3, ... 이다. BFS인 이유 한 지점에서 갈 수 있는 위치 (동일 depth) 를 순차적으로 방문해야 한다. 따라서 가능한 경우의 수를 queue 에 쌓아서 동일 depth 에서 처리해줘야 한다. [프로그래머스] Lv.2 게임 맵 최단거리 (BFS) + 반례 14개, 연습용 좌표판 PDF 게임 맵 최단거리 시작 지점부..

[프로그래머스] Lv.2 게임 맵 최단거리 (BFS) + 반례 14개, 연습용 좌표판 PDF

게임 맵 최단거리 시작 지점부터 도착 지점까지 최단거리로 방문했을 때, 얼마나 걸리는지를 물어보는 문제이다. 예제의 경우 11 이다. 최단거리가 DFS 가 아닌 BFS 인 이유 한 지점에서 갈 수 있는 위치 (동일 depth) 를 순차적으로 방문해야 한다. 따라서 가능한 경우의 수를 queue 에 쌓아서 동일 depth 에서 처리해줘야 한다. DFS 는 동일 depth 를 순차적으로 방문하는 것이 아니라, depth 를 파고들어간다. (계속해서 함수를 호출한다) 따라서 최단경로가 아님에도, 이미 간 길을 그대로 가버린다. 풀이 코드 구조 한 위치(0, 0)에서 시작한다. 다음 위치로 갈 수 있는지 검사한다. (가지치기) 갈 수 있는 위치들에 대해서 후보 리스트(candidates) 를 만든다. 이 때 c..