알고리즘/백준9 백준 18116. 로봇 조립 문제 https://www.acmicpc.net/problem/18116 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 더보기 문제 풀이 Union-Find를 이용해서 서로 다른 부품을 하나의 집합으로 만들어 준다. 군집끼리 union 할 때 부모에게 자식의 부품의 수를 합한다. N은 명령어의 수이지 부품의 번호 범위가 아니다. 소스코드(Java) 더보기 package baek; import java.io.BufferedReader; import java.io.InputStreamReader; import jav.. 2021. 12. 23. 백준 1992. 쿼드트리 문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 더보기 더보기 문제풀이 구역을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 탐색을 하면서 그 구역이 0이나 1로 되어 있거나 사이즈가 1일 때 탐색을 그만하고 0이나 1을 출력하는 문제였다. 구역탐색을 재귀형식으로 시작 행과 시작 열, 사이즈를 받아 탐색을 하는 함수를 만들고, 구역 내에 전부 0이나 1인지 검사하는 check함수를 만들어 사이즈가 1이거나 check함.. 2021. 12. 22. 백준 16562. 친구비 문제 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 문제풀이 학생들을 집합으로 묶을 때 비용을 최솟값으로 저장하면서 풀이가 가능 하다. 그래서 유니온 파인드를 사용해서 풀었다. 1. 친구관계 M개를 입력 받을 때, 학생들을 하나의 집합으로 합쳐준다.(union) 2. 해당집합을 합치면서 최솟값을 저장하고, 한쪽은 0으로 만든다. (union) 3. 저장된 최솟값들을 더한다음 k와 비교하여 k보다 .. 2021. 12. 21. 백준 17836. 공주님을 구해라! 문제 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 문제풀이 모든 경로를 탐색 하면서, 그람의 유무에 따라 경로가 달라질 수 있으므로 두가지 경우를 생각해서 BFS탐색을 사용해 풀었다. Node라는 클래스는 행, 열, 탐색한 시간, 그람의 유무를 가지고 클래스로 만들었다. 방문체크는 3차원 배열 visited를 사용하였고, visited[r][c][0]은 그람을 가지고 있지 않았을 때, visited[r][c][1]은 그람을 가지고 있을 때 방문체크를 나누어서 했다. 탐색시 두가지 경우의 수를.. 2021. 12. 20. 이전 1 2 3 다음
