문제 풀이 1️⃣ 치킨집의 위치와 집의 위치를 미리 찾아서 리스트에 저장합니다. 2️⃣ 치킨집과의 최솟값을 찾아야하므로 변수를 max사이즈로 지정해줍니다. 3️⃣ M개수만큼의 치킨집을 골랐을 때 최솟값을 찾아야하므로 M개의 치킨집을 고르는 조합의 수를 구합니다. 4️⃣ 조합의 수를 구하기위해 브루트포스와 백트래킹 알고리즘을 사용합니다. 5️⃣ dfs 재귀를 반복하면서 조건에 충족됐을 때 집과 치킨집과의 거리를 저장합니다. 6️⃣ 저장한 치킨집과의 거리를 min함수로 저장해서 최솟값을 출력합니다. 전체 코드 from sys import stdin as s s=open('input.txt','rt') def dfs(cur,arr): global answer # arr의 길이가 M과 같으면 아래 조건문 진입 ..

문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이과정 이 문제는 그래프 탐색, bfs, 브루트 포스 알고리즘, 백트래킹 등 여러개의 알고리즘이 섞여있는 문제이다. 우선 어느 경우의 수에서 최대 안전 영역의 개수가 나오는지 모르기 때문에 모든 경우를 탐색하는 수 밖에 없다. 배열의 첫번째부터 벽을 세워나가서 벽의 개수가 3개가 됐을 때 bfs를 실행하고 바이러스를 전염 시키고 나서 안전 영역의 개수를 카운터해서 저장해놓고 제일 큰 값을 나중..