[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net BFS로 두 번째 풀어보는 문제다! DFS를 공부해둔 후 BFS에 접근해보니 생각보다 괜찮은 거 같았다. (물론 이 문제는 실버 2) 문제의 내용은 다음과 같다. 루트 노트는 무조건 1이고 각 노드들의 부모는 누구인지 프린트하는 것이다. 코드 import java.util.*; public class Main { static ArrayList[] map; static boolean[] visit; static int n; static int[] parent; public..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제는 1, 1부터 시작하여 n, m까지의 최단 거리를 BFS로 구하는 것이다. BFS를 공부한 지 얼마 안 돼 디버깅하면서 풀어보니 Queue에 지점을 추가할 때 x좌표, y좌표, 카운트를 넣어줘야 하기 때문에 클래스 하나를 만들어 큐에 넣어줬다. 그리고 여기서 내가 고민했던 것은 만약 막힌 길로 가면 어떻게 해야 하지였는데 생각보다 간단했다. 큐의 구조를 사용하니 큐에서 빼낸 좌표가 막힌 길로 가면 그냥 그거는 없어지면 된다. 그리고..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 문제는 다음과 같다. 그냥 가장 큰 음식물의 크기를 구하는 것이다. DFS로 하나하나 돌려보면서 카운팅 해주면 끝이다! 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { st..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 문제는 잘 설명되어 있지만 여기에서 주의해야 할 게 오른쪽과 아래로만 내려갈 수 있다! 처음에 동서남북으로 다 움직이면서 답이 왜 안 나오지 그러면서 헤매었다.. 코드 import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { static char[][] map; st..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 문제는 다음과 같다. n개의 노드가 주어지고 m번의 거리를 구할 노드와 노드가 한 쌍으로 개수가 주어진다. 그리고 n번째줄까지 a노드와 b노드, 거리가 주어지고 n+1번째 줄부터 n+m번째 줄까지 노드와 노드가 주어진다. 그리고 주어진 노드들 사이의 거리를 구하면 된다. 코드 import java.util.ArrayList; import java.util.Scanner; public class Main { static ArrayList[] map; s..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제는 트리에서 노드 하나를 삭제하고 그 트리의 리프 노드를 구하는 것이다. 그냥 마지막으로 입력받은 노드를 부모 노드에서 삭제시키고 dfs 돌리면 된다. 따라서 쉬운 편인 문제이다. 코드 import java.util.ArrayList; import java.util.Scanner; public class Main { static ArrayList[] map; static boolean[] visi..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제는 다음과 같다. 간선의 길이를 다 합쳤을 때 가장 긴 지름인 두 노드를 구해서 그 지름을 프린트하는 것이다! DFS로 금방 풀 수 있다. 코드 import java.util.ArrayList; import java.util.Scanner; public class Main { static ArrayList[] map; static boolean[] visit; static int n..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 문제는 상하좌우, 대각선으로 숫자 1인 것을 방문해서 카운팅만 해주면 된다. 코드 import java.util.Scanner; public class Main { static boolean[][] map; static boolean[][] visit; static int n; static int m; static int dx[] = {0, 0, -1, 1, -1, 1, -1, 1}; static int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1}; public static void main..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 문제는 W와 B가 주어질 때 상하좌우로 같은 알파벳이라면 그거에 개수만큼 제곱되어 공격력이 된다. 그래서 각각의 공격력을 나타내면 된다. 문제 import java.util.Scanner; public class Main { static char[][] map; static boolean[][] visit; static int n; static int m; static int dx..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 문제는 #으로 된 무리 안에 양이 사는데 늑대가 출몰한다. 이때 무리 안에 양의 수 > 늑대 수일 경우 늑대를 내보낼 수 있고, 늑대 수 >= 양의 수일 경우 늑대는 양을 다 잡아 먹는다. 코드 import java.util.Scanner; public class Main { static char[][] map; static boolean[][] visit; static int r; stati..
