개인사

리뷰다익스트라 라고 보기엔 애매하고 그냥 우선순위 큐를 사용한 BFS 문제 라고 보면 될 것 같다. 문제 풀이n값을 받고 1과 0이 붙어있길래 그냥 string으로 맵 정보를 받아주었다.방향 배열과 방문 처리를 할 배열을 초기화 해준다. 이때 방문 배열은 벽을 뚫은 횟수 기록용 3차 배열로 초기화거리, x좌표, y좌표를 인자로 갖는 구조체 Pos를 초기화 해준다.우선순위 큐에서 정렬용으로 사용할 compare 객체를 초기화 하고, 거리를 기준으로 오름차순으로 정렬해 준다.bfs를 시작하고 0, 0부터 시작해 n-1, n-1에 도달 했을 경우 벽을 부순 횟수를 리턴해 주도록 한다.리턴값을 출력해 주면 된다. 참고 사항bfs함수 내부 구조 상세 설명Pos를 자료구조로 갖고, Pos 내 d를 오름차순으로 정렬..

리뷰1부터 N까지의 최단 경로의 길이를 찾되, 반드시 두 정점을 거친 후 이동 해야하는 문제 문제 풀이노드의 개수 n과 간선의 개수 e를 입력 받고 인접리스트를 나타낼 2차 pair형 벡터 lst를 n + 1크기로 초기화 한다.e개의 간선의 정보를 lst에 양방향 간선으로 추가해 주고, v1와 v2 값을 입력 받아준다.1 => v1 => v2 => N과 1 => v2 => v1 => N의 최단 경로를 각각 구해준다.두 경로 중 더 작은 값을 정답으로 출력하면 된다, 만약 두 경로 모두 INT_MAX라면 -1을 출력해 준다. 참고 사항우선순위 큐의 자료형을 pair를 쓸 경우 greater>를 통해 쉽게 최소힙으로 변환할 수 있다.INT_MAX를 사용해 주기 위해서는 climits를 include를 해줘야..

리뷰다익스트라를 활용하되 최단 경로까지의 시간이 아닌, 최단 경로 중 가장 먼저 밟아야 하는 노드를 출력하는 문제 문제 풀이인접리스트를 n + 1크기로 초기화 해주고 가중치와 시작, 도착 노드를 양방향으로 추가해 준다.이제 각 노드에 대해 해당 노드를 시작점으로 하는 다익스트라를 돌려주면 된다.거리를 나타낼 dist 벡터를 n + 1 크기, 기본값을 10억으로 초기화 해주었다.경로를 나타낼 path 벡터를 n + 1 크기로 초기화 해주었다.최소 힙을 정의해 주고 거리를 0으로 시작 노드를 추가해 준뒤 시작 노드의 거리를 0으로 초기화 해준다.이후 일반적인 다익스트라 로직을 실행 하되, 경로가 갱신되었을 경우 path 벡터를 변경해 준다.만약 현재 노드의 path가 비어있을 경우 다음 노드의 경로에 다음 ..

리뷰특정 노드를 무조건 방문하고, 방문하지 않는 조건을 가진 최단 경로 문제 문제 풀이n, m을 입력 받고 인접 리스트를 n + 1 크기로 초기화 해준 뒤 단방향으로 노드와 가중치를 벡터에 넣어준다.x, y, z를 입력 받고 first에 x 에서 y까지의 최단 경로를 구하고, y부터 z까지의 최단 경로를 구한 뒤 더해준다.second에 x부터 z까지 최단 경로를 구해준다. 이때 bfs에 flag를 전달 해 y를 들릴지 말지를 정해준다.bfs가 실행되면 n + 1크기의 거리 배열을 매우 큰 값으로 초기화 해준 뒤 최소힙을 만들어 준다.시작 위치를 힙에 넣고, 거리를 0으로 초기화 해준 뒤 while 루프를 돌려준다.만약 bfs에 전달된 flag가 0이라면 기존 bfs를 진행, flag가 1이라면 다음 노드..

리뷰문제 정보가 좀 애매해서 정답 도출에 어려움을 겪었다, 그냥 다익스트라로 s 부터 t까지의 최단 경로를 구하면 된다. 문제 풀이n, m값을 입력 받고 인접 리스트를 n + 1 크기로, 거리 벡터를 n + 1, 값을 최대한 크게 설정해 준다.연결이란 두 정점이 간선을 통해 방문 가능하다고 문제에 쓰여있으니 양방향 이동이 가능하다.시작 노드와 목적지 노드를 입력 받고 시작 노드를 힙에 추가, 시작노드의 거리를 0으로 초기화 한다.while 루프를 시작해 시작 노드로 부터 각 노드까지의 최단 경로를 찾아 준다.이후 목적지 까지의 노드를 출력해 주면 된다. 참고 사항특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 ..

리뷰오랜만의 파이썬 풀이였는데 C++을 주로 쓰다보니 이제 파이썬이 익숙치 않아 큰일이다.. 문제 풀이일반적인 다익스트라 풀이로 쭉 진행한다.인접리스트를 n + 1크기로 초기화 후 단방향으로 값을 받아준다.거리 리스트를 적당히 큰 값으로 설정하고 n + 1 크기로 초기화 해준다.경로를 나타낼 path 배열을 0 값으로 n + 1크기로 초기화 해준다.시작 위치의 거리를 0으로, 힙을 세팅해 주고 while문을 돌려준다.힙에서 pop한 현재 노드를 기준으로 인접리스트를 돌고 만약 현재 까지 구한 해당 노드까지의 거리보다 현재 거리가 더 작을경우 갱신해 준다.이때 path 배열의 다음 노드 인덱스에 현재 노드를 넣어준다. 이후 갱신한 거리와 다음 노드를 힙에 추가해준다.while 루프가 끝난 후 우선 목적지 ..

리뷰C++, 파이썬 모두 힙을 사용한 BFS로 문제를 풀었다. 문제 풀이m과 n을 입력받고 2차 배열을 입력 받는다, 방향 배열을 4방향으로 초기화 한 후 방문 배열도 n * m크기로 초기화 한다.힙에 (벽을 부순 횟수, x좌표, y좌표)를 초기화 해준다. 초기값은 (0, 0, 0)이다. 최소 벽을 출력할 min_wall 변수도 0으로 초기화 해주고 while 루프를 실행한다.현재 힙에 존재하는 벽이 가장 낮은 정보를 뽑아온다.만약 끝부분에 도달했다면 현재 까지 부순 벽의 수를 min_wall에 저장해 준다.그게 아니라면 4방향을 체크하며 범위 내에 존재하는지, 방문을 한적이 있는지를 체크해 준다.만약 방문을 하지 않은 좌표라면 방문 처리를 해주고, 해당 좌표의 값이 1이라면 부순 벽을 1만큼 올려준 뒤..

리뷰출력에서 예제 테스트용인 인덱스 5를 넣었다가 한번 틀려버렸다 ㅠ 문제 풀이n, m값을 받아주고 e는 빈 리스트를 n + 1개, dist는 INF 를 n + 1개로 초기화 해준다.m개 줄에 a, b, c를 받아주고 a번 노드에 거리 c와 도착지점 b를 리스트로 추가해 준다.start와 end가 될 도시의 정보를 받아와 주고 힙에 [0, start]를, start 도시의 거리를 0으로 초기화 해준다.while루프를 시작하여 현재 누적 거리보다 더 빠른 거리가 있을 경우 해당 도시까지의 거리를 최신화 해준다.while루프를 마친 후 end 도시까지의 거리를 dist[end]를 통해 출력해 준다. 참고 사항마지막줄에 시작 도시와 도착 도시의 정보가 있으니 꼭 참고하자  정답 코드import sysimpor..

리뷰다익스트라를 사용해 푸는 문제, 메모리 시간 살발하다 C++로도 풀어봐야되는데 엄두가 안나네.. 문제 풀이n, m, k, x값을 모두 받아온다.각노드의 간선을 나타낼 빈 리스트를 n + 1개로 초기화 해준다.각 노드까지의 거리를 나타낼 리스트를 INF값을 갖는 n + 1개로 초기화 해준다.m개의 간선 정보를 각 노드에 추가해 준다. 이때 거리는 1로 고정이므로 [1, 다음 노드]의 형식으로 추가해 줬다.힙에 시작 노드와 거리 0을 넣어주고 현재 노드에서 현재 노드까지의 거리는 0으로 설정해 준다.while루프를 돌며 각 간선까지의 거리 정보를 최신화 해주고 힙에 추가해주는 작업을 해준다.루프 종료 후 거리가 k인 도시가 있다면 모두 출력해 주고 없다면 -1을 출력해 준다. 참고 사항while루프 내에..

리뷰다익스트라를 활용한 문제 풀이 문제 풀이노드의 개수 n와 간선의 개수 m를 받아오고 시작점 k을 받아온다.각 노드의 간선 정보를 edge 리스트에 초기화 해준다. 인덱스 참조를 위해 n + 1 개의 빈 리스트를 2중 리스트로 생성각 노드까지의 거리를 나타낼 dist 리스트를 초기화 해준다. 마찬가지로 n + 1 개의 INF값으로 생성해 준다.m개의 간선 정보를 받아온다, 각 노드 시작점에 [거리, 노드] 형식의 리스트를 추가해 준다.시작점이 될 힙을 거리 0, 시작노드 k로 초기화 해주고, 시작 위치의 거리를 0으로 변경해 준다.힙이 존재할때 까지 while루프를 돌아 최소 힙을 pop해주고 현재 거리와 노드를 뽑아내 준다.만약 현재 거리가 dist에 저장된 현재 노드의 거리와 다를 경우 contin..