IT Crowd

문제풀이 2차원 배열의 특정 위치에서 부터 인접 좌표들로 이동을 하면서 최소비용을 구하는 문제 가중치가 없다면 단순 bfs로 해결할 수 있음. 문제에서는 현재좌표의 높이와 새로운 좌표의 높이 차이가 있다면 ( 새로운 좌표가 높다면) 그 높이 만큼을 가중치로 계산함 시작점 (0,0)에서 BFS 탐색을 하면서 각 인접 좌표 (상하좌우)에 대해 간선완화를 진행 한 좌표의 상하좌우에 있는 새로운 좌표 계산 각 좌표가 범위내인지 확인 새로운 좌표의 높이가 현재의 높이보다 높다면 그 차이를 가중치로 계산 높이 차이가 없거나 새좌표가 더 낮으면 가중치는 1 (기본 비용) 새로운 좌표의 현재까지의 최소비용(시작점에서 부터의 최소비용)가 현 좌표를 찍고 가는 것 보다 높으면 새로운 비용으로 갱신 새좌표의 최소비용 > 현..

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://swexpertacademy.com/ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 자세한 문제의 내용은 위 사이트의 수록된 문제로 5521. 상원이의 생일파티 를 검색하여 문제를 확인하면 된다. 문제풀이 상원이가 생일파티에 자신과 친한 친구와 친한친구의 친한친구에게 초대장을 주는 상황 그래프로 표현할 수 있음 나눠 줘야하는 초대장의 수를 구하는 문제이고 1번이 상원이임. 그래프를 탐색하여 해결할 수 있고, 탐색 시작이 1번임을 알 수 있음. 친한친구의 친한친구까지 탐색 너비우선탐색 (BFS)을 이용하여 해결할 수 있고, 탐색의 너비를 2로 제한함. que에 담긴 요소의 갯수를 저장하고 이를 이..

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..