문제 링크 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 - BFS 활용하여 X 부터 다른 노드까지의 거리 배열 구한 후 K에 해당하는 거리값을 가지는 노드 오름차순으로 풀이 - 간선의 비용이 1이기 때문에 최단 거리가 아닌 BFS 만으로도 풀이 가능 *실수 1) 거리 배열(DIST)를 최대값으로 초기화 하지 않은 것 Arrays.fill(DIST, Integer...

문제 링크 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 - 3차원 배열의 그래프 탐색 문제 - 필드 초기화시 가로,세로,높이 변수가 혼란스러워 시간소요함 (그외에는 문제에서 요구하는 바와 같이 그대로 풀이하면 됨) - multisource bfs로 토마토(1)의 위치를 찾고, 위치값을 0으로 초기화(나머지는 -1) - 상하좌우위아래로 격자형 그래프 풀 듯이 이동하면서 위치값을 갱신하여 마지막에 최대값 찾으면 됨 ..

문제 링크 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 - BFS, DFS 로 문제 풀이 - 시간복잡도 : O(N^2) - 방문 배열과 같이 부모 배열 선언하고 연결된 노드의 부모 노드 정보를 갱신해주면 쉽게 풀리는 문제 제출 코드 BFS 로 할 경우 import java.util.*; import java.io.*; public class Main { static StringBuilder sb = new StringBuilder(); static int N; static List[] adj; st..

문제 링크 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 - 단방향 그래프 문제 예제 입력의 경우 아래와 같이 해석됨 예제 입력 1 3 0 1 0 0 0 1 1 0 0 예제 출력1 1 1 1 1 1 1 1 1 1 #정점(N)이 3개이고 간선이 존재한다는 뜻 1 -> 2 2 -> 3 3 -> 1 그래서 i = 1일때 1번 노드에서 방문 가능한 노드를 찾고 row 로 출력하면 되는 문제 i = 2일때 2번 노드에서 방문가능한 노드 찾아 row 출력 i = 3일때 3번 ..

문제 링크 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 - 양방향 그래프로 문제 풀이 - 방문 배열 사용하여 1번부터 연결된 정점에 대해 방문 처리 - 방문한 경우 바이러스 전파 된 것이므로 카운팅하여 결과 출력 제출 코드 - bfs, dfs 둘 다 정의 import java.util.*; import java.io.*; public class Main { static int N, LINE; static List[] adj; static b..

문제 링크 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 - 전형적인 격자형 그래프 문제 - 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. - '.' (점)은 빈 필드를, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미 - 상하좌우로만 이동가능하며, 울타리는 이동 불가 - (조건) 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 - 전형적인 격자형 그래프 탐색 문제 - 방문배열을 사용하여, 방문하지 않고 배추가 심어져 있는 경우 상하좌우 방문처리하면서 그룹 카운팅 수행 - 가로, 세로 (5≤N≤25) 길이가 최대인 경우 시간복잡도는 O(N^2) = O(625) 이므로 Integer 처리 가능 제출 코드 - bfs, dfs 둘 다 정의 import java.util.*; import java.io.*; public cl..

문제 링크 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 - 전형적인 그래프 탐색 문제 - 방향없는 그래프 키워드에서 양방향 그래프라 생각하고 인접 리스트에 정점, 간선 데이터 입력 - 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) - 최대 N = 1,000, M = 1000*999/2 = 499500 ..

문제 링크 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 - 전형적인 격자형 그래프 탐색 문제 - 방문 배열과 배추가 심어져 있는 배열을 가지고 그룹 카운트 수행 - 방문하지 않고, 배추가 심어져 있는 경우 카운터를 하나 올리고 상하좌우 탐색하면서 방문처리 - Test Case별 시간복잡도 : O(N^2) 제출 코드 DFS의 경우 import java.io.*; import java.util.*; public class Main { static St..

문제 링크 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 - 전형적인 격자형 그래프 탐색 문제 - 테스트 케이스별로 초기화 및 섬의 개수 카운팅 수행 - 정점에서 움직일 수 있는 방향은 8가지 (상하좌우, 대각선 양방향) - N은 최대 50 - 시간 복잡도 : O(N^2) , 테스트 케이스별로 O(2500) 씩 걸림 w, h 입력 값이 조금 헷갈리고, 테스트 케이스 처리만 번거로웠지 나머지는 그래프 탐색 기본 유형과 동일했음 제출 ..

문제 링크 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 - 첫번째 줄에 맵의 크기 R, C 주어짐 (최대 50) - 비어있는 곳은 '.' / 물이 차있는 지역은 '*' / 돌은 'X' / 비버의 굴은 'D' / 고슴도치의 위치는 'S' 로 표시 - 격자형 그래프 탐색 문제 (상하좌우) - 물 '*'은 매 분마다 비어있는 인접 칸으로 확장 - 물(*)과 고슴도치(S)는 돌을 통과할 수 없음 - 고슴도치(S)는 물(*)이 차있는 구역으로 이동할 수 없..

문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 - 현재 위치, 상태(숫자)를 정점으로 보고 +1 , -1, *2 를 간선이라 정의하여 문제 풀이 - BFS 문제 풀이 - N = 100,000 이고, K = 0 인 경우 -1 을 10만번 하면 K에 도착함 => 최대치 100,000 이므로 Integer 풀이 가능 제출 코드 import java.util.*; import java.io.*; public..

문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 - 첫번째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8) - 0은 빈 칸, 1은 벽, 2는 바이러스 위치 아래의 절차와 같이 진행한다 1) 빈칸(0) 위치에 벽을 3개 세운다 2) 바이러스를 전파(방문)한다 3) 바이러스가 전파(방문)하지 않은 빈칸(0) 영역을 카운팅하여 최대 결과값을 찾는다. 최대 맵의 크기가 8 * 8 = 64일때 3개의 벽을 찾는 조합의 수 ..

문제 링크 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 풀이 - 문제에는 표현되어 있지 않지만, 물통의 상태(=정점), 물을 붙는 행위 (=간선) 으로 정의하여 풀어야 하는 그래프 문제 1) 입력으로 A B C 물통의 사이즈가 정해짐 2) 초기 C 물통만 가득찬 상태이고, 나머지 비어있는 상태에서 시작 3) 각각 다른 물통에 물을 붙는 행위를 하여 A = 0 일때 C 물통의 상태(결과)값을 구해 오름차순으로 출력 이때 정..