본문 바로가기
728x90

그래프64

[python] 백준 14442 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 해결 (0,0)에서 (n-1,m-1)까지 이동하는 문제 갈 수 있는 길이 있고 없는 길이 있다. 하지만 예외적으로 k번 갈 수 없는 길을 갈 수 있다. 따라서 visited[i][j]에서 예외포인트 k번 까지 가능하다는 것에서 visited[i][j][k]의 방문 여부를 확인하는 것이 편하다. visited[i][j][k]의 값은 (i,j)까지 벽을 깰 수.. 2023. 3. 14.
[python] 백준 1965 상자넣기 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제 해결 이전의 상자들이 영향을 주기 때문에 dp 이용해야 한다는 느낌이 든다. 하지만 어느 상자를 마지막에 넣어야 할 지는 잘 알 수 없다. 마지막에 넣을 수 있는 상자의 인덱스를 미리 알아본다. (for문을 통해) dp[i]를 i상자 안에 있는 최대 상자 개수라고 하면 for문을 통해 i보다 작은 인덱스 상자 중 넣을 수 있는 상자 최대 개수와 dp[i]를 비교해가며 최댓값으로 dp[i]를 수정해간다.. 2023. 3. 12.
[python] 백준 14502 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 벽을 어떻게 세워야하는가? → 상황에 따라 다르다. So 모든 경우 다 해봐야 한다. 재귀 사용! 최대 영역을 어떻게 구하는가? 전염 되는 지역을 계속 이동 시킨 후 더이상 전염이 안될 때 전염이 안된 일반 지역의 구역 개수를 구하면 된다. 전염지역 구하기 위해 bfs() 할 때 계속 graph 값이 바뀌므로 copy.deepcopy를 이용해 복사본으로 돌리는 것이 좋다! copy 라이브러리 알아두.. 2023. 3. 6.
[python] 백준 5639 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 해결 전위 순회(preorder)한 노드의 value 값을 리스트 안에 차례대로 받는다. 인덱스를 차례대로 키워가며 노드의 value 값이 이전보다 작으면 깊이를 늘리지 않고 오른쪽 자식 값으로 가는 규칙이 있다. 이 트리를 후위 순회(postorder)한 결과를 출력하는 것이 문제 인덱스를 이용하여 후위 순회 함수를 만들면 된다. 중간에 노드의 value 값이 이전보다 작아 더.. 2023. 3. 5.
728x90