문제 링크 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 물통의 상태(결과)값을 구해 오름차순으로 출력 이때 정..

문제 링크 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 - 시간복잡도 O(NlogN) = 정렬 O(NlogN) 후 투 포인터 O(N) 수행 - Integer 범위 내이긴 하지만, 초기화시 일부 long 선언 처리 - M 만큼의 차이가 날 때까지 R을 먼저 탐색, A[R] - A[L] > M 조건 성립시 결과값 갱신 (최소값) 제출 코드 import java.util.*; import java.io.*; public ..

문제 링크 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 풀이 - 시간복잡도 O(N) - 1 (라이언 인형) 인 경우에만 카운팅 처리를 해주고, K개이상이 되는 연속된 인형의 집합의 길이는 L, R범위로 측정 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, K; static int[] A; static void input() throws Excep..

문제 링크 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 - 정렬 후 투 포인터 로직 수행 - 시간 복잡도 : O(NlogN) - 배열 순차적으로 순회하여 기준 값과 나머지 영역에서 투 포인터로 두 값을 정하고 다 더했을 때 0에 가까운 최대 값을 구하면 됨 참고 [BOJ 2470] 두용액 (Java, 투 포인터) [BOJ 1253] 좋다 (Java, 투 포인터) 제출 코드 - 입력 배열 A 의 데이터 타입을 lon..

문제 링크 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 풀이 - 알파벳(26자) 카운팅 배열을 활용하여 투포인터 문제 풀이 - 시간복잡도는 O(N) *알파벳 인덱스 구하기 int index = TEXT.char(i) - 'a'; 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, CNT; static String TEXT; static int[] ALPHABET ..

문제 링크 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 - 두 용액 문제 풀이 방법을 응용하여 풀이 - 시간 복잡도 O(NlogN) - 순차 조회하면서 해당 값을 다른 두 수의 합으로 만들 수 있는지 확인 (이때 탐색과정에서 자기자신의 경우 제외, targetIdx) 제출 코드 import java.util.*; import java.io.*; public class Main { static int N; static int[] A; static void input..

문제 링크 https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 - 투 포인트 기법과 카운팅 배열을 활용하여 1 ~ N 까지의 모든 경우의 수 합을 더하면 됨 - 시간복잡도 O(N) 이때 최대값의 경우 1 2 3 ... 100,000 1 2 3 ... 100,000 1 ~ 100,000까지의 합을 나타내기 때문에 100000(99999) / 2 = 대략 50억이기 때문에 long으로 풀이 해야 함 L = 1인 경우 100,000 L = 2인 경우 99..