문제 www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 역시 삼성 SW A형 문제답게 브루트 포스문제였다. 거기에 그래프 탐색이 더해졌다. 이 문제 또한 2가지의 부분 문제로 나눠볼 수 있다. 1) 선거구를 어떻게 나눌 것인가 2) 어떻게 그래프 탐색을 할 것인가 1) 선거구를 어떻게 나눌 것인가 조합을 사용하여 선거구를 나눈다. 이때 n의 절반(1~n//2)만큼만 조합을 구하면 된다. 이는 mCn = n-mCn이 성립하는 조합의 성질을 잘 생각해보면 알 수 있다. 즉, 한 ..
그래프 순회란? 그래프 순회란 그래프 탐색(Search)라고도 일컫으며 그래프의 각 정점을 방문하는 과정을 의미하며, 크게 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)으로 나뉜다. DFS는 주로 스택이나 재귀로 구현하며 백트래킹 알고리즘에 사용된다. 반면에 BFS는 주로 큐로 구현하며 그래프의 최단 경로를 구하는 문제 등에 사용된다. 깊이 우선 탐색(DFS) 일반적으로 DFS는 스택으로 구현하며, 재귀를 이용하면 좀 더 간단하게 구현할 수 있다. 실제로 코딩 테스트에서는 재귀를 이용한 구현이 더 선호되는 편이다. 재귀적 구조로 구현 먼저 재귀 구조로 DFS를 구현해보자. 슈도코드는 다음과 같다. RecursiveDFS(v)..
문제 www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 일반적인 그래프 탐색 문제와 달리 z축까지 고려해야 하는 문제였다.최소 일수, 즉 최단 거리를 구해야 하기 때문에 BFS를 이용해야 한다. 모든 익은 토마토의 좌표를 큐에 담아주는 것이 중요하다. 어느 지점에서 탐색을 시작하는지 여부에 따라 최단 거리가 상이하게 구해지기 때문이다. 코드 import sys, collections def bfs(): result = 0 q = c..
문제 www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이 처음엔 단순한 그래프 문제로 생각했는데, 잘 풀리지 않았다. 곰곰히 생각해보니 이전에 프로그래머스에서 풀었던 등굣길 문제와 유사했다. 좌표 (0, 0)부터 (n-1, n-1)까지 순회하며 현재 좌표(x, y)에서 오른쪽과 아래쪽으로 갈 수 있는지 검사하고, 만약 갈 수 있다면 dp[nx][ny]에 dp[x][y]를 더해준다. 이때 dp[y][x] == 0이면 건너뛰는 방식으로 최적화를 해줄..
문제 www.acmicpc.net/problem/2644 풀이 BFS로 풀이했다. 거리(촌수)를 구해야 할 두 노드가 정해져 있기 때문에 시작 노드만 큐에 넣고 탐색을 했다. 코드 import sys, collections def bfs(start, end): q = collections.deque([]) q.append([start,0]) visited[start] = 1 while q: cur, cnt = q.popleft() if cur == end: print(cnt) return for adj in g[cur]: if not visited[adj]: visited[adj] = 1 q.append([adj,cnt+1]) print(-1) n = int(sys.stdin.readline().stri..
