시리즈

문제풀이

1.백준 1197 최소 스패닝 트리

문제 링크 크루스칼과 union-find를 이용해 트리를 만드는 문제 간선 정보를 입력받은 후 가중치를 기준으로 정렬했다. 이후 union-find를 이용해 공통 조상으로 묶어주며, 묶을 때마다 가중치를 더해주고 완료 후 해당 값을 반환했다.

2023년 10월 2일

2.백준 1600 말이 되고픈 원숭이

https://www.acmicpc.net/problem/1600 체스 타일 하나하나를 노드로 둔다. 나이트 이동 횟수를 3차원 배열의 축으로 둔다. 한번 이동할 때마다 내려간다. 나이트 이동을 제외한 상하좌우를 이동하는걸 구현한다.

2023년 10월 2일

https://www.acmicpc.net/problem/2109 정렬을 이용하면 되지만 우선순위 큐를 사용했다. 처음에는 지정된 날짜에만 강연할 수 있다고 생각했으나, 그 이전에도 강연할 수 있었다. p를 기준으로 최대 우선순위큐를 만들고 비어있는 날짜에 계속해서 채워주었다. 만약 d 날짜에 강연이 비어있을 경우 p로 채워준다. 그렇지 않을 경우, 1일...

2023년 10월 2일

4.백준 17090 미로 탈출하기

https://www.acmicpc.net/problem/17090 bfs 사용 시 내 머리가 꼬일 것 같아서 관뒀다. 정점에 주어진 방향이 정해져 있기 때문에 얌전히 dfs 썼다. 탐색 시 두 가지 경우로 나뉜다. 탈출 가능한 정점인 경우: escape를 갱신한다. 다른 정점으로 이동하는 경우: 다른 정점을 탐색한 후 해당 결과를 현재 정점에도 적용한...

2023년 10월 2일

5.백준 10775 공항

https://www.acmicpc.net/problem/10775 순차 탐색을 그리디(?)하게 탐색하는 방식을 사용해서 풀었다. (???) 게이트에 도킹하는 규칙은 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트 중 하나에 도킹하는 것이므로, gi부터 1번 순으로 도킹하는 게 가장 효율적이다. 1번부터 채울 시, n번 비행기가 m번째 게이트에 도킹할...

2023년 10월 5일