[C++] 백준 10282번 해킹

다익스트라의 기초적인 문제.

 

다익스트라란?

 

그래프에서 시작점이 있을 때, 시작점에서부터 최단 거리로 한 점씩 이동해보며 해당 점의 최소거리를 확정해 나가는 알고리즘이다. 이 때, 특정 점에서 다른 점들까지의 거리를 구한다는 뜻은 그 특정 점까지의 최단 거리는 확정됐다는 뜻이다. 그래프 이론에서 중요한 알고리즘이다. 이 때 모든 간선치는 양의 정수라고 가정한다.

 

다익스트라는 머리로는 그리기가 쉬운데, C++에서 구현하려면 복잡한 문법을 많이 알아야 한다.

내 구현 기준으로는

1. pair<T, T> : pair 자료형은 특정 자료형 두개를 동시에 저장할 수 있다. make_pair(1, 2) 혹은 {1, 2} 이런 식으로 사용 가능하다.
2. priority_queue<T, container, comparator> : 우선순위 큐는 T 자료형을 container(vector 등)의 형태로 담고 comparator(greater:오름차순, less:내림차순)로 비교해서 저장한다.

queue 정렬을 찾았는데 priority_queue가 있었다.

사용한 STL과 변수

 

vector STL과 priority_queue 사용을 위한 queue STL을 사용했다.

그래프 구현을 위해 adj 이차원 벡터가 있는데 이 때 pair 자료형을 사용했다.

입력을 받는 변수들과 총 감염된 컴퓨터의 개수인 infested_num, 최대시간 변수인 max_cost가 있고

시작점에서부터 해당 점까지의 cost를 나타내는 com_cost 배열, 그리고 확정됐는지 안됐는지 보는

visit배열이 있다.

 

다익스트라 메서드

다익스트라 메서드에서는 처음에 우선순위 큐를 선언하고 시작점을 push한다.

이 때 pair의 first가 cost가 되게 해야 cost에 따라 자동으로 오름차순 정렬이 된다.

그리고 시작점의 비용은 0이므로 0으로 push한다.

pq가 비어있지 않을 때 까지 다익스트라를 진행하며,

내가 pop한 컴퓨터의 번호가 이미 최단거리가 확정된 번호라면 continue로 넘어간다.

아니라면 해당 컴퓨터번호를 최단거리로 확정짓고, 감염된 컴퓨터 수를 증가시킨다.

그리고 현재 코스트가 max_cost보다 크다면 업데이트한다.

adj 그래프에서 현재 컴퓨터 번호를 보면서 다음 번호와 비용을 검사한다.

만일 com_cost 배열에 저장된 비용보다 현재 구한 비용이 싸다면 com_cost 배열을 업데이트하고

pq에 push한다.

(비용은 당연히 시간을 의미한다.)

내가 가는 방향은 무조건 최단거리 이고 pq에서 자동으로 cost에 따라 정렬해주므로

최단거리가 아닌 확정되는 점은 나오지 않는다.

 

테스트 케이스가 여러 개이므로 초기화 함수를 만든다.

처음에 adj.clear()를 그냥 써버려서 오류가 났다.

이차원 벡터이므로 adj[인덱스] 마다 clear() 해줘야한다

 

메인 함수

메인 함수에서는 테케를 입력받고 매 테케마다 초기화 함수를 실행시키고 컴퓨터 개수, 인접 개수, 시작 번호를 입력받는다.

인접 번호를 입력 받는데 이 때 나는 양방향 그래프로 만들었는데 문제에 의존한다는 뜻이 처음에 무엇인지 몰랐는데 잘 보니 단방향 그래프를 의미하는 것이었다.

a가 b에 의존한다는 뜻은 b->a 라는 뜻이었다.

그렇게 입력받고 다익스트라 메서드를 실행시키고 결과변수들을 출력한다.

처음에 양방향으로 만들었는데 이상하게 답이 맞게 나왔다. (맞게 나온건 아니고 어거지로 때려맞추다 보니 맞게 나왔다.)

 

단방향으로 바꿨더니 깔끔하게 예제도 잘 출력됐다.

 

kimyunseok/study-record

코드 전문은 위에서 확인 가능하다.

 

다익스트라를 오랜만에 풀었는데 확실히 많이 까먹었다.

종종 많이 풀어야겠다고 생각했다.