공부하자

13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 두 가지 방법으로 풀 수 있다! 다익스트라 (Heap, Priority Queue 활용) 0-1 BFS (Deque 활용) 다익스트라는 힙에서 다음 위치를 꺼낼 때 우선순위를 고려해야하므로, (걸린 시간, 위치)의 형태로 삽입을 하게 된다. 이에 반해 BFS는 가중치(수빈이가 다음 위치로 가는 데 걸리는 시간, 여기서는 0과 1뿐이다.)에 따라 큐에 삽입하는 위치를 달리해서 위의..

1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 문제 특정 출발점으로부터 특정 도착점까지의 최소비용을 묻고 있기 때문에, 하나의 출발점에 대한 비용행렬을 만들면 된다!! (1차원 행렬) 📢 주의해야 하는 점 방향 그래프이다!! (처음에 무방향 그래프라고 생각했다가 틀렸다...😥) 한 노드로부터 다른 노드로 가는 간선이 여러 개일 수 있다!! 예를 들어, 입력이 다음과 같이 주어지면, 1 2 3 1 2 10 비용이..

20208번: 진우의 민트초코우유 (acmicpc.net) 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 백트래킹, 브루트포스 주어지는 보드 위에 장애물이 없기 때문에, 우유가 있는 위치까지의 맨하탄 거리를 계산하면 된다. 네 방향으로 탐색하는 알고리즘은 시간초과가 발생하게 된다. 아래와 같은 과정으로 풀이했다. 보드 상의 우유 위치를 리스트에 저장한다. 우유 리스트를 순회하며 다음 조건을 검사한다. 현재까지 마시지 않은 우유인가 현재 체력으로 도달할 수 있는 위치인가 두 조건을 만족하면 ..