개인사

리뷰 https://www.acmicpc.net/problem/14461D 최단 경로 문제, 알고리즘 분류에 DP가 있긴 한데, 다익스트라를 통해 문제를 풀이하였다. 전역 변수n, d : 주어지는 지름길의 개수 n, 목적지 까지의 거리 dPos : 다익스트라를 진행할 때 직선 상에서의 현재 위치를 나타낼 구조체, 시간을 기준으로 오름차순 정렬한다.lst : 지름길 정보를 저장하기 위한 pair 타입의 벡터, 최대 10001크기로 설정한ㄷ. 함수1. dijkstraint dijkstra() 다익스트라를 통해 목표 지점까지의 최단 경로를 구하는 함수정수형 벡터 dist를 d + 1 크기, 적당히 큰 값으로 초기화 한다, 나는 20억으로 세팅했다.시작 지점인 0을 dist[0] = 0을 통해 거리를 0으로 만..

리뷰 2차원 다익스트라의 기본적인 문제https://www.acmicpc.net/problem/4485 전역 변수n : 각 테스트 케이스마다 주어지는 맵의 한 변의 길이lst : 각 테스트 케이스마다 주어지는 맵 정보를 저장할 2차원 정수 배열, 최대크기는 125*125다.dx, dy : 상하좌우 4방향을 탐색하기 위한 방향 배열Pos : 우선순위 큐에서 현재 위치 정보를 나타낼 구조체, w를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() 다익스트라를 통해 출발지에서 도착지까지의 최단 거리를 구하는 함수Pos타입 우선순위 큐 pq를 초기화 하고 거기에 시작 지점 x, y좌표와 시작 지점의 값을 넣어준다.n * n크기의 2차원 정수형 벡터 dist를 기본값을 매우 크게 지정..

리뷰 간단한 다익스트라를 통한 시작점 > 도착점으로 가는 최단 경로를 구하는 문제https://www.acmicpc.net/problem/5972 전역 변수n, m : 노드의 개수를 저장할 정수형 변수 n, 간선 개수를 저장할 정수형 변수 mPos : 간선 정보를 저장할 구조체, 다음 노드와 가중치가 저장되며, 우선순위 큐의 compare 함수를 정의했다.path : 각 노드의 인접리스트를 저장할 Pos타입 2차원 벡터 함수1. dijkstraint dijkstra(int start, int end) start에서 end까지의 최단 경로를 구하는 함수Pos타입 우선순위 큐 pq에 start를 삽입하고 end까지 가는길의 최단경로를 dist벡터에 최신화 해준다.pq가 빌때까지 while루프를 통해 위 작업..

리뷰경로 상에 신호등이 있어 기다렸다가 움직여야 하는 최단 경로 문제, 다른 문제와 다른점은 신호등의 방향이 정해져 있어 교차로에 진입하는 경우를 잘 분배해 주어야 했다.https://www.acmicpc.net/problem/1400 문제 풀이행 범위n, 열 범위 m, 시작 좌표 sx, sy 도착 좌표 ex, ey, 방향 배열, 맵 정보 lst배열을 전역 변수로 세팅한다.우선 순위 큐에서 사용할 Pos구조체를 정의하고, compare함수도 넣어준다.신호등 정보를 받을 구조체 Light를 정의하고, 신호등 배열 lights를 60크기로 설정해 준다.main함수에서 무한루프를 실행하고 input함수에서 n, m이 0, 0이라면 while루프를 종료해 준다.input함수를 통해 n, m값을 받고 만약 n과 ..

리뷰 정수형 변수 타입을 잘 확인하자.. 처음에 틀리고 나서 모두 long long으로 바꿔줬으나 다익스트라 리턴 형식을 int로 두었었다.https://www.acmicpc.net/problem/24042 문제 풀이n, m을 지역변수로 설정한다, long long타입 거리 배열을 10만 1 크기로 초기화 해준다.시뮬레이션 상에서 현재 위치 정보가 될 Pos구조체를 정의해 준다. pq를 활용할 것이니 내부에 compare 함수 포함인접 리스트를 표시할 EDGE 구조체를 정의해 준다, 노드와 해당 노드의 신호등 인덱스 정보가 담긴다.EDGE타입의 2차 배열 path를 초기화 해준다. 해당 벡터를 통해 인접리스트를 체크할 것이다.n과 m을 입력 받고 path의 사이즈를 n + 1로 초기화 해준 뒤 거리 배열..

개요특징특정 노드에서 연결 되어 있는 모든 노드까지의 최단 거리를 구할 수 있다.가중치는 양수여야만 하며 음수일 경우 해당 간선을 계속 방문하게 되어 루프에 빠지게 된다.양방향 및 단방향 그래프 및 2차 배열 형태에서도 에 모두 사용 가능하다.동작 요약모든 노드 까지의 거리를 2e9 혹은 INT_MAX와 같은 값을 사용하여 최대치로 설정한다.시작점 노드 자기 자신 까지의 거리를 0으로 설정하고, 우선순위 큐에 자신을 추가한다.첫 탐색 시 자신과 연결된 인접 리스트를 참고하여 해당 노드까지의 거리가 현재 거리보다 짧다면 갱신해 주고 해당 노드를 우선순위 큐에 넣어준다.이후 우선순위 큐에 있는 노드와 연결된 인접 리스트를 참고하여 거리 정보가 최소가 되도록 갱신해 주는 작업을 반복한다.우선순위 큐에 더 이상..

리뷰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를 해줘야..