그래프

[백준] 9370. 미확인 도착지 (Java)

문제 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 알고리즘 그래프, 다익스트라 풀이 다음은 문제에서 주어진 예제 입력의 두번째 케이스를 시각화한 그래프이다. 2번 지점에서 출발하여, 1-3 혹은 3-1 도로를 지나 5번, 혹은 6번 지점으로 갈 수 있다. 이 문제에 대한 정답은 6이다. 2번 지점에서 6번 지점으로 최단 경로로 가려면 2-1-3-6 으로 1-3을 지나가야하기 때문이고, 5번 지점에서 6번 지점으로 최단 경로로 가려면 2-5 로 1-3 혹은 3-1을 지나가지 않기 때문이다. 따라서 시작..

[백준] 21736. 헌내기는 친구가 필요해 (Java)

문제 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 알고리즘 그래프, 너비우선탐색(BFS) 풀이 도연이의 위치 (x,y)에서 시작하여 상하좌우로 너비우선탐색을 진행하며 만난 사람(P)의 수를 센다. 이때, 그래프에 P를 O로 바꾸어 입력해야함에 주의한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java...

[백준] 16940. BFS 스페셜 저지 (Java)

문제 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 알고리즘 그래프, 너비 우선 탐색(BFS), 해시셋 풀이 다음 그래프에 대해 (1 2 3 4 5 6 7 8 9 10 11 12) 라는 방문 순서가 있다면 다음과 같이 판별할 수 있다. 시작 노드인 1이 3개의 인접 노드를 가지고 있으므로 다음 3개의 수(2~4번째)는 1의 인접 노드이어야한다. 그 다음 노드인 2가 2개의 인접 노드를 가지고 있으므로 다음 2개의 수(5~6번째)는 2의 인접 노드이어야한다. ... 모든 노드가 위 조건을 만족하면 올바른 순서임을 알 수 있다. 표로 나타내면 다음과 같다. 빨간색 숫자가 검사할 숫자 파란색 숫자가 그의 인접한 노드가 위치해야하는..

[백준] 12946. 육각보드 (Java)

문제 12946번: 육각 보드 크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다. 육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다. 어떤 칸 www.acmicpc.net 알고리즘 그래프, 깊이우선탐색(DFS) 풀이 육각 보드이므로 인접한 칸이 [상,하,좌,우]가 아니라 [상, 우상, 좌, 우, 하, 우하] 6가지이고, 임의의 칸과 인접한 6칸이 모두 색칠되어야하는 경우 3가지 색이면 모두 색칠할 수 있으므로 정답은 최대 3이 된다. 따라서 X인 칸을 시작으로 DFS를 진행하며 색을 칠한다. 색은 칠하지 않은 경우 0, 색칠된 경우 1, -1 로 표현한다. 인접한 칸이 아직 칠해지지 않았다면 칠해야하므로 ..

[백준] 16947. 서울 지하철 2호선 (Java)

문제 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 알고리즘 그래프, 깊이우선탐색(DFS), 너비우선탐색(BFS) 풀이 DFS를 통해 사이클(순환선)을 찾아 표시하고, BFS를 통해 사이클이 아닌 노드에서 사이클인 노드까지 최소 거리를 구해 문제를 해결하였다. 사이클 찾기 ( DFS ) 모든 역은 연결되어있으므로 임의의 한 역에서 출발하여 DFS로 모든 간선을 탐색한다. 이때 이미 방문한 노드를 다시 방문한다면 사이클이 있는 것이므로 해당 노드까지 다시 되돌아가며 그 사이 역들을 모..

[백준] 16929. Two Dots (Java)

문제 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 알고리즘 그래프, 깊이우선탐색(DFS) 풀이 그래프에 같은 색으로 이루어진 사이클이 있는지 찾는 문제이다. 사이클은 점의 개수가 4보다 크거나 같아야하며 마지막 점이 출발 점과 같은 색이어야한다. 따라서 그래프의 각 점을 출발점으로 하여 DFS를 진행해 사이클이 발생하는 점이 있는지 확인한다. DFS를 위한 재귀 함수의 매개변수로 시작점의 좌표, 현재 점의 좌표, 지나온 점의 개수를 전달한다. 함수의 흐름은 다음과 같다. 현재 점과 인접한 점 (ny..

[백준] 16948. 데스 나이트 (Java)

문제 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 알고리즘 그래프, 너비우선탐색(BFS) 풀이 기존 사방으로 탐색했던 BFS 과정을 문제에서 주어진 6 방향으로 바꾸기만 하면 되는 문제이다. 좌표와 이동 횟수를 큐에 삽입해 6 방향으로 탐색하며 (r2,c2)에 도달했다면 그때의 이동 횟수를 출력하고 도달하지 못하고 BFS 가 종료되었다면 -1 을 출력한다. * 큐에 삽입하므로 최소 이동 횟수가 적은 상태부터 탐색한다. 따라서 도달..

[백준] 1707. 이분 그래프 (Java)

문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 알고리즘 그래프, 이분 그래프, 너비우선탐색(BFS) 풀이 인접한 정점의 색이 칠해져있지 않다면 현재 정점의 색과 반대로 칠해가면서 인접한 정점과 현재 정점의 색이 같은 경우가 생긴다면 이분 그래프가 아니므로 NO를 출력한다. 정점의 개수가 최대 20,000개, 간선의 개수가 최대 200,000개이므로 O(V2) 의 시간, 공간 복잡도를 갖는 인접 행렬이 아닌 O(V+E)의 시간, 공간 복잡도를 갖는 인접 리스트를 사용한다. 각 정점의 색을 저장할 colo..

[백준] 13023. ABCDE (Java)

문제 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 알고리즘 그래프, 깊이우선탐색(DFS) 풀이 그래프의 최대 깊이가 4보다 크거나 같으면 1을, 아니면 0을 반환하는 문제이다. 노드의 수, 간선의 수가 모두 최대 2,000 이므로 O(V2) 의 시간 복잡도, 공간 복잡도를 갖는 인접 행렬보다 O(V+E)의 시간 복잡도, 공간 복잡도를 갖는 인접 리스트로 표현하는 것이 훨씬 효율적이다. 입력을 받아 양방향 인접 리스트 형태로 그래프를 만들고, 각 노드를 출발 노드로 하여 dfs를 반복한다. dfs 를 이용해 현재 노드와 연결된 노드를 탐색하며 깊이를 1씩 늘린다. 깊이가 4가 되면 1을 출력하고 프로그램을 종료한다..

[백준] 2422. 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (Java)

문제 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 알고리즘 브루트포스, 조합, 그래프 풀이 아이스크림이 수가 최대인 200일 때, 아이스크림을 고르는 경우의 수는 200C3 = 200 * 199 * 198 / 6 = 약 130만이다. 130만 개의 경우의 수마다 최대 10000개에 해당하는 섞어먹으면 안되는 조합을 일일이 검사하면 130만 * 1만으로 시간 초과가 난다. 따라서 2차원 배열로 그래프를 만들어 섞어먹으면 안되는 조합인지 O(1)에 알 수 있도록 한다. [..