BangBang's Devlogs

www.acmicpc.net/problem/1181 문제 해결 방안 1. HashSet을 이용하여 입력을 받아 중복된 경우를 제거해준다. 2. ArrayList에 담아서 해당 ArrayList를 Collections.sort()를 이용하여 정렬해준다. 이 때, new Comparator를 사용하여 길이가 짧은 것과 길이가 같으면 사전순으로 정렬하는 코드를 구현해준다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashSet; import jav..

www.acmicpc.net/problem/7568 문제 해결 방안 전체 경우의 수를 비교해보면 되는 간단한 문제이다. 완전탐색을 이용하여 peoples i번째의 키와 몸무게를 다른 j번째 키와 몸무게를 비교하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; // 덩치 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.rea..

www.acmicpc.net/problem/2667 문제 해결 방안 total이 단지 수가 되고 지도를 탐색하면서 1을 발견하면 total++을 해준다. 그리고 DFS탐색으로 통해 해당 단지에 속한 집의 갯수를 cnt에 저장하여 dfs()를 빠져나오면 ArrayList에 해당 cnt를 넣어준다. 그리고 ArrayList에 저장된 각 단지의 집의 갯수들을 정렬하여 출력해주면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import ..

www.acmicpc.net/problem/1012 문제 해결 방안 배추가 있는 공간들을 DFS 탐색을 통해 분리된 갯수를 찾는 문제이다. maps에 배추가 있는 값들을 추가해주고 maps를 탐색하면서 1(배추가 있는 곳)일 때 result(지렁이)++해주고 DFS를 해서 visited를 true로 만들어줘서 다음에 1일때 이미 방문했으면 넘어갈 수 있게 해주었다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; //유기농 배추 public class Main { static int m; // 가로길이(1~50) static int n; // 세로길이(1~50) static int ..

www.acmicpc.net/problem/2178 문제 미로의 (1,1) 에서 (n,m)위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다. BFS + DP를 이용하여 해결하였다. 해결 방안 1. 미로의 이동 가능 여부 관련 값은 maps[][]에 저장하였다.(1이면 이동 가능) 미로의 해당 칸으로 이동할 때 지나야하는 최소의 칸 수는 cnts[][]에 저장하였다.(0이면 한번도 이동 안한 곳) 2. 주어진 maps의 (1,1) 위치에서 (m,n)으로 BFS 방법으로 4방향을 탐색하고 DP를 이용하여 cnts에 지나야하는 최소 칸 수를 메모제이션하였다. 3. cnts[n][m]을 출력하면 도착 위치에 가기위해 지나야하는 최소의 칸을 출력한다. 코드 import java.io.BufferedR..

www.acmicpc.net/problem/2606 문제 입력의 첫째 줄이 그래프의 노드 갯수가 되고 둘째 줄이 간선의 갯수가 될 것이다. 또한 무방향 그래프가 될것이다. 해결 방안 무방향 그래프를 ArrayList를 이용하여 구현하였다. 1번부터 시작하는 DFS 탐색을 하였으며 DFS의 depth를 바이러스 감염 시킨 컴퓨터 갯수로 하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; // 바이러스 public class Main { static int n; // v static int e; // edge static Array..

www.acmicpc.net/problem/10974 문제 해결 방안 모든 순열을 출력하는 기본적인 DFS 문제이다. DFS + 백트래킹을 이용하여 구현하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; // 모든 순열 public class Main { static int n; static boolean[] visited; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 문제 해결 방안 time 배열의 index는 해당 위치이고 값은 해당 위치를 수빈이가 최소 몇 초를 나타낸다. 또한 수빈이는 3가지 방법으로 이동할 수 있으므로 3가지 방법으로 이동한 위치의 값이 k 일때까지 너비우선 탐색을 해주면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.In..

www.acmicpc.net/problem/1766 문제 * 위상 정렬의 대표적인 문제이다. (줄 세우기 문제에 약간 심화문제 우선순위 큐 사용) yubh1017.tistory.com/manage/newpost/83?type=post&returnURL=https%3A%2F%2Fyubh1017.tistory.com%2F83 Queue를 이용한 위상정렬로 구현하였다. 문제를 풀기전 간단하게 위상정렬에 대한 설명을 하자면 1. 위상 정렬은 그래프 정렬을 말한다. 2. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다. 두 노드 A,B 사이에 A->B 같은 관계가 성립되어야 하며 A->B 관계가 성립하면 B->A나 B->C->A와 같이 사..

www.acmicpc.net/problem/2252 문제 * 위상 정렬의 대표적인 문제이다. Queue를 이용한 위상정렬로 구현하였다. 문제를 풀기전 간단하게 위상정렬에 대한 설명을 하자면 1. 위상 정렬은 그래프 정렬을 말한다. 2. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다. 두 노드 A,B 사이에 A->B 같은 관계가 성립되어야 하며 A->B 관계가 성립하면 B->A나 B->C->A와 같이 사이클이 생겨서는 안된다. 3. 자기 자신을 가리키는 간선의 갯수인 indegree 배열을 이용하여 구현할 수 있다. 4. 위상 정렬 과정 4.1) 위상 정렬을 위해 두개의 Queue를 만들어준다. q : indegree 값이 0인 ..