그래프 탐색32 [백준 14442] 벽 부수고 이동하기 2 [Java] 풀이 [백준 2206] 벽 부수고 이동하기 [Java] 풀이 (0, 0)에서 (N - 1, M - 1)까지 최대 벽을 1개 부수며 도착할 수 있는 최단거리를 구하면 되는 문제다. 하나의 2차원 배열에 최단거리를 기록하기에는 어느 순간 벽을 부술때와 부수지 않는 경우 kyr-db.tistory.com 위 문제의 확장 버전이다. 벽을 최대 K개 부수며 이동할 수 있다. 이전 로직에서 탐색 중 벽이 아닌 부분을 만났을 때 처리하는 부분을 0 또는 1이 아니라, 지금까지 부순 횟수(smash) + 1로 변경해 처리해주자. 그리고 마찬가지로, 벽을 0 ~ 10개 부순 경우에 대한 이동경로를 기록해야 하니 2개가 아닌, K+1개로 아래처럼 공간을 할당해 주자. 소스코드 소스코드 보기 출처 14442번: 벽 부수고 .. 2023. 7. 15. [백준 1939] 중량제한 [Java] 풀이 출발지(from)와 목적지(to)에 대해 연결된 다리 중 최대중량을 구하는 문제다. 입력받은 다리의 중량제한에 대해 내림차순 정렬 후 순서대로 union시키며, from과 to가 동일한 집합에 속하는지(연결됬는지) 확인해주어 연결된 순간 union한 간선의 가중치가 최대 가중치이므로 출력하면 된다. 소스코드 소스코드 보기 출처 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 2023. 7. 9. [백준 2206] 벽 부수고 이동하기 [Java] 풀이 (0, 0)에서 (N - 1, M - 1)까지 최대 벽을 1개 부수며 도착할 수 있는 최단거리를 구하면 되는 문제다. 하나의 2차원 배열에 최단거리를 기록하기에는 어느 순간 벽을 부술때와 부수지 않는 경우 중 어떤 경우가 더 빨리 도달할지 기록하기 어렵다. 때문에 두 경우에 대해 최단거리를 기록하고, 가장 먼저 (N - 1, M - 1)에 도달한 경우의 최단거리를 출력해주면 된다. 2차원 배열을 벽을 부수는 경우와 부수지 않는 경우로 하지 않고, queue에 넣어줄 때 현재의 최단거리를 가지고 있는 Point객체를 넣어주는 방식으로 풀이했다. bfs를 진행하며 다음 영역이 벽이 아니라면, 벽을 부순경우와 부수지 않은 경우 모두 아무 제한 없이 queue에 넣어주면 된다. 만약 다음 영역이 벽이라면,.. 2023. 7. 9. [백준 1976] 여행 가자 [Java] 풀이 이전에 풀었던 문제의 확장판이다. [백준 17352] 여러분의 다리가 되어 드리겠습니다! [Java] 풀이 N + 1개의 집합 1 ~ N에 대해 공통 부모가 다른 경우를 찾아 연결해주면 되는 문제다. 우선, 입력으로 두 집합을 입력받아 union해주자. 모든 입력을 받았다면, parents에 자신의 부모 집합의 번호 kyr-db.tistory.com 입력에 따라 union을 해주고, 최대 1000개 까지 주어지는 최대 200이하의 도시에 대해 여행계획이 가능한지, 즉 공통 부모가 다르지 않은지 확인하는 문제다. 입력받은 i번째 줄의 j번이 1이라면 i 에서 j는 연결된 도시이다. 마지막에 입력되는 여행 계획은 결국 도시들이 하나로 연결이 되어있는지 여부에 따라 여행 가능 여부가 결정된다. 즉, 공통.. 2023. 6. 29. [백준 17352] 여러분의 다리가 되어 드리겠습니다! [Java] 풀이 N + 1개의 집합 1 ~ N에 대해 공통 부모가 다른 경우를 찾아 연결해주면 되는 문제다. 우선, 입력으로 두 집합을 입력받아 union해주자. 모든 입력을 받았다면, parents에 자신의 부모 집합의 번호가 적혀있을 것이다. 반복문을 돌며, 부모 집합의 번호가 다르다면 두 집합은 연결되어 있지 않으므로 두 집합을 연결할 수 있도록 번호를 출력해주면 되는 문제다. 소스코드 소스코드 보기 출처 2023. 6. 29. [백준 28270] Marked-Numbered [Python] 풀이 트리로 주어지는 목차의 정보를 글머리 번호 형태로 바꾸면 되는 문제다. 아래 조건에 따라 변환할 수 있다. i 번째 수가 i - 1번째 수보다 작다면, 상위 글머리 번호부터 변환해주어야 한다. i 번째 수가 i - 1번째 수보다 크다면, 글머리 번호 형태에 따라 1로 변해야 한다. i 번째 수가 i - 1번째 수와 동일하다면, 이미 존재하는 목차이므로 i - 1번째 수의 글머리 번호 형태 + 1로 변해야 한다. 먼저 i번째 수가 i - 1번째 수보다 작은 경우다. 상위 글머리 번호부터 변환해주어야 하기에 이전에 기록된 하위 글머리 번호에 대해 누적된 수들을 0으로 초기화 하는 과정이 시간초과의 원인이 되었다. 이번 기회에 알게 된 사실인데, 문제를 틀렸거나 부분점수를 얻은 경우 '내 제출' 란에서 .. 2023. 6. 25. 이전 1 2 3 4 ··· 6 다음
