본문 바로가기

DFS10

[백준] 2250: 트리의 높이와 너비 - 중위 순회로 열 번호 구하기 (Java) 문제 바로가기트리를 직접 격자에 그릴 필요는 없다이진 트리를 문제의 규칙대로 격자에 배치했을 때, 너비가 가장 넓은 레벨과 그 너비를 구하는 문제다.처음에는 각 서브트리의 크기를 구한 뒤 노드의 열을 계산해야 한다고 생각했다. 하지만 배치 규칙을 살펴보면 왼쪽 서브트리의 노드는 부모보다 왼쪽에 있고, 오른쪽 서브트리의 노드는 부모보다 오른쪽에 있다.이 순서는 중위 순회의 방문 순서와 같다.왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리중위 순회로 노드를 방문하면서 1부터 열 번호를 부여하면, 별도의 격자를 만들지 않고도 각 노드가 놓일 열을 구할 수 있다.입력 순서와 노드 번호로 루트를 판단하면 안 된다입력은 각 노드의 번호, 왼쪽 자식과 오른쪽 자식을 알려 준다. 첫 번째로 입력된 노드나 번호가 1인 .. 2024. 5. 14.
[백준] 13325: 이진 트리 - 후위 순회로 루트와 리프 사이 거리 맞추기 (Java) 문제 바로가기모든 루트에서 리프까지의 거리를 같게 만든다포화 이진 트리의 각 간선에 가중치가 있다. 간선 가중치를 증가시켜 루트에서 모든 리프까지의 거리를 같게 만들고, 변경한 뒤 전체 간선 가중치의 합을 최소화해야 한다.가중치는 줄일 수 없고 늘릴 수만 있다. 따라서 한 노드의 왼쪽과 오른쪽 경로 길이가 다르면 긴 쪽을 줄이는 것이 아니라 짧은 쪽을 긴 쪽에 맞춰야 한다.왼쪽 경로 길이 = 7오른쪽 경로 길이 = 10최소 증가량 = 10 - 7 = 3맞춘 뒤 길이 = 10이 판단은 자식 서브트리 안의 경로가 먼저 같은 길이로 정리돼 있어야 가능하다. 그래서 리프부터 루트 방향으로 결과를 올리는 후위 순회를 사용했다.간선 가중치를 자식 노드에 저장한다문제에서는 간선에 가중치가 있지만, 배열에서는 해당 .. 2024. 5. 14.
[백준] 15681: 트리와 쿼리 - DFS와 트리 DP로 서브트리 크기 미리 구하기 (Java) 문제 바로가기질문마다 같은 하위 정점을 다시 세지 않는다트리의 간선과 루트 R이 주어진다. 각 질문에서는 정점 U를 루트로 하는 서브트리에 정점이 몇 개 있는지 구해야 한다. U 자신도 개수에 포함한다.나는 질문마다 DFS를 다시 실행하면 같은 정점을 반복해서 세게 된다고 생각했다. 트리와 루트가 질문 사이에 바뀌지 않으므로, R에서 DFS를 한 번 실행해 모든 정점의 서브트리 크기를 저장했다.전처리: 루트 R에서 DFS → 모든 정점의 서브트리 크기 저장질문: dp[U] 조회 → 바로 출력여기서 U를 기준으로 트리 전체의 루트를 다시 정하는 것은 아니다. R을 기준으로 정해진 부모와 자식 관계에서 U와 그 자손만 세는 것이다.서브트리 크기는 자신 1개와 자식들의 크기의 합이다상태를 다음과 같이 정의.. 2024. 5. 13.
[백준] 24230: 트리 색칠하기 - DFS와 그리디로 색이 바뀌는 경계 세기 (Java) 문제 바로가기한 번 칠하면 서브트리 전체의 색이 바뀐다1번 정점을 루트로 하는 트리에서 처음에는 모든 정점의 색이 0이다. 정점 하나를 선택해 색칠하면 그 정점과 모든 자손이 같은 색으로 바뀐다. 주어진 목표 색을 만드는 데 필요한 최소 색칠 횟수를 구해야 한다.나는 루트부터 DFS로 내려가며 부모에게 물려받은 색과 현재 정점의 목표 색을 비교했다. 두 색이 같으면 그대로 내려가고, 다르면 현재 정점에서 한 번 칠한 것으로 처리했다.서브트리의 정점을 매번 찾아 실제로 바꿀 필요는 없다. 자식으로 이동할 때 부모의 색을 전달하면 앞선 색칠의 영향을 표현할 수 있다.부모에게 물려받은 색만 확인하면 된다제출 코드에서는 목표 색을 color에, DFS 과정에서 적용한 색을 arr에 저장했다.값의미color[no.. 2024. 5. 13.
[백준] 16947: 서울 지하철 2호선 - DFS로 순환선을 찾고 BFS로 거리 구하기 (Java) 문제 바로가기순환선을 먼저 찾아야 거리를 구할 수 있다노선은 하나의 순환선과 그 순환선에 붙은 지선으로 구성된다. 각 역에서 순환선까지의 최소 거리를 출력해야 하며, 순환선에 포함된 역의 거리는 0이다.나는 풀이를 두 단계로 나눴다. 먼저 DFS로 순환선에 속한 역을 표시하고, 표시된 역에서 BFS를 시작해 지선의 거리를 계산했다.DFS: 순환선에 포함된 역 표시 ↓BFS: 순환선에서 지선으로 이동하며 거리 계산순환선을 이루는 역 중 하나만 찾는 것으로는 부족하다. 거리 0인 모든 역을 구분해야 지선을 탐색할 때 순환선 내부를 이동한 거리를 잘못 더하지 않는다.무방향 그래프에서 부모로 돌아가는 간선은 순환이 아니다역 사이 연결은 양방향이므로 인접 리스트에도 두 방향을 저장했다.list.get(a)... 2024. 5. 13.
[백준] 1937: 욕심쟁이 판다 - DFS와 메모이제이션으로 최장 경로 구하기 (Java) 문제 바로가기모든 칸에서 시작할 수 있는 최장 경로 문제판다는 대나무가 있는 한 칸에서 시작해 상하좌우로 이동한다. 다음 칸의 대나무 수가 현재 칸보다 많을 때만 이동할 수 있다. 조건을 만족하며 방문할 수 있는 최대 칸 수를 구해야 한다.시작점이 정해져 있지 않으므로 모든 칸을 시작점으로 확인해야 한다.정답 = 모든 칸에서 시작한 이동 가능 칸 수의 최댓값처음에는 각 칸에서 단순 DFS를 실행했다. 같은 칸에 도착한 뒤의 경로를 여러 시작점에서 계속 다시 탐색하면서 시간 초과가 발생했다.예를 들어 여러 낮은 칸이 하나의 높은 칸으로 모이면, 높은 칸부터 이어지는 경로는 항상 같은데도 시작점마다 다시 계산한다. 그래서 각 칸에서 출발했을 때 이동할 수 있는 최대 칸 수를 저장해 재사용했다.dp의 의미를 .. 2024. 5. 12.
[백준] 15683: 감시 - DFS 완전 탐색과 시뮬레이션으로 사각지대 최소화하기 (Java) 문제 바로가기CCTV 하나의 최선이 전체의 최선은 아니다CCTV의 방향을 정해 감시하지 못하는 빈칸 수를 최소화하는 문제다. 감시 방향에 있는 벽을 만나면 멈추지만, 다른 CCTV는 통과할 수 있다.CCTV마다 가장 많은 빈칸을 보는 방향만 고르면 될 것 같지만, 감시 영역이 겹칠 수 있다. 한 CCTV가 넓게 보는 방향보다 다른 CCTV가 보지 못하는 곳을 담당하는 방향이 전체 사각지대를 더 줄일 수도 있다.그래서 나는 각 CCTV의 방향을 모두 정한 뒤, 그 배치를 실제로 적용해 사각지대를 계산했다. 방향 선택은 DFS로, 감시 영역 계산은 시뮬레이션으로 분리한 풀이다.종류별로 서로 다른 회전만 탐색한다방향 번호는 오른쪽부터 시계방향으로 정했다.0: 오른쪽1: 아래쪽2: 왼쪽3: 위쪽static in.. 2024. 5. 12.
[백준] 2251: 물통 - 물의 양을 상태로 저장하는 DFS와 총량 보존 (Java) 문제 바로가기물을 옮기는 순서가 아니라 현재 물의 양을 기억한다용량이 A, B, C인 물통이 있고, 처음에는 C 물통에만 물이 가득 들어 있다. 한 물통에서 다른 물통으로 옮길 때는 보내는 물통이 비거나 받는 물통이 가득 찰 때까지 붓는다.가능한 모든 이동을 거친 상태 중에서 A 물통이 비어 있을 때 C 물통에 남을 수 있는 물의 양을 구해야 한다.나는 각 물통에 들어 있는 양을 (a, b, c)로 저장하고 DFS로 탐색했다. 어떤 순서로 도착했든 세 물통의 양이 같으면 이후 가능한 이동도 같으므로, 같은 상태는 한 번만 탐색하면 된다.기호의미A, B, C각 물통의 최대 용량a, b, c현재 각 물통에 들어 있는 양대문자와 소문자를 구분해야 남은 공간과 옮길 양을 계산할 때 혼동하지 않는다.한 번에 옮기.. 2024. 5. 12.
[백준] 12919: A와 B 2 - 역방향 탐색으로 가능한 연산 줄이기 (Java) https://www.acmicpc.net/problem/12919문자열을 늘리는 대신 줄여 보기A와 B로 이루어진 문자열 S에 다음 두 연산을 적용해 T를 만들 수 있는지 판단하는 문제다.문자열 뒤에 A를 추가한다.문자열 뒤에 B를 추가한 다음 전체를 뒤집는다.나는 S에서 시작해 문자열을 늘리는 대신, T에서 마지막 연산을 되돌리며 S를 찾았다. 정방향에서는 매번 두 연산을 시도할 수 있지만, 역방향에서는 현재 문자열의 첫 글자와 마지막 글자를 보고 불가능한 연산을 제외할 수 있기 때문이다.문자열의 길이가 S와 같아질 때까지 줄인 뒤, 내용까지 일치하면 1을 출력한다.두 연산을 어떻게 되돌릴까이전 문자열을 X라고 하면 각 연산의 결과와 역연산은 다음과 같다.정방향 연산결과의 특징역방향 처리X 뒤에 A .. 2024. 5. 12.
[백준] 3980: 선발 명단 - 백트래킹과 비트마스킹으로 포지션 배정하기 (Java) https://www.acmicpc.net/problem/3980한 선수의 최고 능력치보다 전체 배정이 중요하다11명의 선수를 서로 다른 11개 포지션에 배치해 능력치 합을 최대화하는 문제다. 선수마다 포지션별 능력치가 다르고, 능력치가 0인 포지션에는 배치할 수 없다.나는 선수를 한 명씩 순서대로 처리하면서 가능한 포지션을 선택하는 DFS를 사용했다. 이미 사용한 포지션은 비트마스크로 기록하고, 11명 모두 배정했을 때만 정답을 갱신했다.핵심은 지금 선수에게 가장 좋은 포지션이 팀 전체에도 가장 좋은 선택인 것은 아니라는 점이다.가장 큰 값부터 고르면 왜 안 될까세 선수와 세 포지션으로 줄여 생각해 보자.선수포지션 A포지션 B포지션 C선수 11090선수 2800선수 3076선수 1을 능력치가 가장 높은.. 2024. 5. 11.

티스토리툴바