본문 바로가기
728x90

DFS37

[python] 백준 3109 빵집 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 문제 해결 우선 0열 전체가 근처 빵집 가스관이고 c-1열 전체가 원웅이 빵집 가스관이다. 한번에 1열씩 이동한다. 행으로는 -1,0,1행 움직일 수 있다. 0행부터 r-1행까지 조사한다고 할 때 겹치지 않는 최대한 많은 파이프를 만들려면 -1행으로 움직이는 길을 만들수록 좋다. 차선책이 0행이고 악의수는 밑으로 1행 움직이는 것이다. 파이프 하나 완성시킬 때마다 +1 씩 정답이 증가한다. 파이프를 연결하는 과정.. 2023. 3. 16.
[python] 백준 1937 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 해결 계속해서 그래프 안을 상하좌우 움직이고 갔단 곳은 안가므로(숫자가 증가 수열이므로) DFS 사용하는 것이 좋을 것이다. 그런데 그냥 쓰면 당연히 시간초과가 날 것이다. 이전에 방문해서 결과를 냈던 것은 저장을 하는 것이 필요하다. 그러기 위해서는 dp를 사용해서 이전에 (r,c) 좌표에서 DFS 시작했을 때 최댓값이 dp[r][c] 였다.라고 저장되어있으면 넘어간다. CODE.. 2023. 3. 10.
[python] 백준 14502 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 벽을 어떻게 세워야하는가? → 상황에 따라 다르다. So 모든 경우 다 해봐야 한다. 재귀 사용! 최대 영역을 어떻게 구하는가? 전염 되는 지역을 계속 이동 시킨 후 더이상 전염이 안될 때 전염이 안된 일반 지역의 구역 개수를 구하면 된다. 전염지역 구하기 위해 bfs() 할 때 계속 graph 값이 바뀌므로 copy.deepcopy를 이용해 복사본으로 돌리는 것이 좋다! copy 라이브러리 알아두.. 2023. 3. 6.
[python] 백준 2023 신기한 소수 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 풀이 두자리 이상일때(n≥2) 맨 앞자리는 소수만 가능(2,3,5,7) 나머지 자리는 홀수만 가능(1,3,5,7,9) 그래서 앞자리 만드는 것 부터 시작.(2, 3, 5, 7) 그 다음 수를 이어 붙일 때 소수인지 확인하고 소수이면 이어붙이고 아니면 다른 수 찾기 n자리 수가 되었을 때 출력 전형적인 DFS로 풀 수 있다. CODE import sys sys.setrecursion.. 2023. 2. 22.
728x90