[C++, DFS, Bitmask] 백준 17471번 게리맨더링 문제풀이
문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 해설 비트마스크라는 참신한 풀이법을 익힌 문제이다. 그래프 문제에서 유용하게 쓰일 수 있는 기법을 발견했다. 선거구 즉, 총 노드의 개수만큼 비트를 할당하여 방문할 노드 선정하는 방법이다. 코드에서 i는 노드에 방문할 총 가짓수를 나타내고 j는 실제 방문한 노드를 나타내어 dfs기법으로 각 노드를 탐색한다. 여기서 특정할 만한 건 i를 반전시켜 2개로 나눈 그룹의 인구를 다시 빼준다는 것이다. 끝에 모두 방문했는..
2019. 10. 4.
[C++,구현,BFS,DFS] 백준 15686번 치킨 배달 문제풀이
문제링크 백준 15686번 치킨 배달 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net DFS,BFS를 모두 쓴 조금은 힘든? 문제이다. 최대 M개의 치킨집을 고르는 건 DFS, 치킨집을 골라 최소거리를 구하는 건 BFS로 구현하였다. 밑에 코드에 나..
2019. 5. 25.