IT Crowd

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제풀이 공기와 2변 이상 접촉한 치즈가 사라지는데 치즈가 모두 녹는데 걸리는 시간 구하는 문제 탐색 (bfs) 문제 공기 접촉면이 2인 구역을 찾아야함 : find 함수로 구현 찾은 치즈를 녹이고 녹인 치즈 갯수 알아냄 : melt 함수로 구현 find함수와 melt 함수를 반복해서 실행하고 녹인 치즈가 0개이면 종료하고 그 때 시간을 알아냄 find 함수 0,0 좌표에서 부터 bfs ..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제풀이 입력으로 받은 인접 정보를 이용해서 인접행렬을 구성함 1~N까지의 도시번호를 이용해서 부분집합(power set) 을 구하고 선택된 집합을 A, 아닌 집합을 B로 묶음 도시집합 A,B의 길이가 0이 아니고 집합들이 모두 연결되어 있다면(bfs탐색으로 알아냄) 각 집합의 인구 총합을 구하고, 그의 차를 계산하여 그 중 최소 값을 찾음 각 집합 도시 연결 확인하기 각 도시 집합에 대해서 bfs 탐색을 수행하여 연..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 문제풀이 BFS 탐색 문제 날짜에 따라서 잠긴부분과 아닌 부분을 0과 1로 나타냄 그 다음, 1 인 부분(잠기지 않은 부분) 을 bfs 탐색으로 찾아내어 카운팅함 각 날짜별로 계산해서 그 중 최대 영역 개수를 찾아냄 코드 (python) dir=[[-1,0],[0,1],[1,0],[0,-1]] def bfs(start): que = [] que.append(start) map_b[start[0]][s..