분리집합

https://www.acmicpc.net/problem/27945문제 요약1번부터 N번까지의 요리 학원이 존재요리 학원 사이에는 M개의 양방향길이 존재키위새는 이제 매일 노점에 들러 가지 디저트를 먹지 않으면 쓰러지게 된다N - 1개의 길을 골랐을 때, 키위새가 쓰러지는 날을 d일 차로 할 때, d의 최댓값 구하기시간 제한1초입력요리학원 수 N과 길의 수 M1 ≤ N ≤ 10만M개의 줄에 연결된 두 학원의 번호와 노점이 여는날 ti가 주어짐각 요리 학원에서 길을 따라 모든 요리 학원으로 가는 방법이 존재하는 경우만 주어진다.두 요리 학원 사이의 길은 많아야 하나이다ti는 모두 다르다출력d의 최댓값 출력접근법키위새는 1일차부터 매일매일 길 사이에 위치한 노점에 방문해야 하고, N-1개의 길만 갈 수 있다..

알고리즘 문제) PG [PCCP 기출문제] 2번 / 석유 시추 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 요약세로길이 N, 가로길이 M인 격자 모양 땅 속에 석유 발견석유는 여러 덩어리로 나뉘어 묻힘가장 많은 석유를 뽑을 수 있는 시추관 위치를 찾으려 한다시추관은 특정 열을 관통하는 형태이다.이때, 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 RETURN입력2차원 배열 형태로 땅 정보가 주어짐 (0 : 빈 땅, 1 :..

알고리즘 문제) BOJ 14725. 개미굴 링크 : https://www.acmicpc.net/problem/14725문제 요약로봇 개미로부터 얻은 개미굴 저장소를 바탕으로, 개미굴 구조를 출력해라예를들어, 아래와 같은 정보를 받았다면KIWI BANANAKIWI APPLEAPPLE APPLEAPPLE BANANA KIWI아래처럼 출력해라 APPLE --APPLE --BANANA ----KIWI KIWI --APPLE --BANANA개미굴의 각 층은 "--" 로 구분하며, 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다시간 제한1초입력첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개두 번째 줄부터 N+1 번째 ..

알고리즘 문제) BOJ 1043. 거짓말 링크 : https://www.acmicpc.net/problem/1043문제 요약지연이는 거짓말하는 걸 좋아한다.파티에가서 거짓말을 하기 위해서는, 진실을 아는 사람이 있으면 안되고, 진실을 아는 사람과 같은 파티였던 사람이 있는 곳도 안된다.이때, 거짓말을 할 수 있는 파티 개수는?시간 제한2초입력사람 수 N, 파티 수 MN과 M은 50이하 자연수진실을 아는 사람 수와 사람의 번호가 주어짐사람의 번호는 1~N진실을 아는 사람 수는 0이상 50이하 정수M개의 줄에는 각 파티마다 오는 사람 수와 사람 번호가 차례로 주어진다.각 파티에 오는 사람 수는 1이상 50이하 정수출력거짓말을 할 수 있는 파티 개수접근법UNION & FIND로 풀었다,같은 파티에 참석한 경우..

알고리즘 문제) BOJ 4179. 불! 링크 : https://www.acmicpc.net/problem/4179문제 요약지훈이가 불에서 타기 전에 얼마나 빨리 탈출할 수 있는지 판단하기불은 매 분마다 한칸씩 수평, 수직으로 이동(네방향 확산)지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다지훈이와 불은 벽을 통과할 수 없다시간 제한1초입력R C1 ≤ R,C ≤ 1000행, 열R개의 줄에 맵이 주어짐‘#’ : 벽‘.’ : 빈칸‘J’ : 지훈이 초기 위치‘F’ : 블이 난 공간J는 입력에서 하나만 주어진다.출력지훈이가 미로를 탈출 할 수 없다면 IMPOSSIBLE가능하다면, 가장 빠른 탈출 시간 출력접근법bfs 알고리즘 사용우선 지훈이가 이동 가능한 경우는 여러 케이스가 있다큐에 bfs를 돌며 이동..

알고리즘 문제) BOJ 17251. 힘 겨루기 링크 : https://www.acmicpc.net/problem/17251문제 요약N명의 선수가 일렬로 있고, 1번부터 N-1까지 수가 적힌 공을 무작위로 뽑아 기준선으로 정하려함예를 들어 3번 공을 뽑으면 3번과 4번 사이가 기준성기준선 왼쪽은 R팀, 오른쪽은 B팀이때, 각 팀에서 가장 센 사람이 나오고 힘을 겨룬다.이때 힘이 더 센 사람이 이긴다.이길 확률이 높은 팀을 찾아라!시간 제한1초입력사람의 수 N이 주어진다.N은 1,000,000보다 작거나 같은 짝수1번 사람부터 N번 사람까지의 힘을 나타내는 정수각 사람의 힘은 10,000보다 작거나 같은 자연수출력이길 확률이 높은 팀을 출력 R 또는 B만약 같다면 X 출력접근법prefix배열과 suffix ..

알고리즘 문제) BOJ 2350. 대운하 링크 : https://www.acmicpc.net/problem/2350문제 요약N개의 도시 존재, M개의 운하 건설K개의 노선 준비각 노선의 도시 i와 j간을 운행하는 배는 도시 i와 j간 경로에 포함된 운하를 통과할 수 있어야 함배는 배의 크기 이상 폭의 운하만 통과가 가능하다K개의 줄에 각 노선을 운행할 수 있는 최대 배의 폭을 출력시간 제한1초입력도시의 수 N, 운하의 수 M, 노선의 수 KN ≤ 1000,M ≤ 100000,K ≤ 10000M개의 줄에는 세 정수 i, j, w도시 i와 j 사이에 폭이 w인 운하를 건설할 것임을 의미1 ≤ i, j ≤ N, w ≤ 200K개의 줄에는 각 노선이 연결하는 도시 i, j1 ≤ i, j ≤N출력K개의 줄에 각 ..

알고리즘 문제) BOJ 1368. 물대기 링크 : https://www.acmicpc.net/problem/1368문제 요약N개의 논에 물을 대려고 한다.물을 대는 방법에는 두 가지가 존재직접 논에 우물을 파는 것이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 것각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때, 논에 물을 대는 최소 비용 찾기시간 제한2초입력첫째 줄 : 논의 수N1 ≤ N ≤ 300다음 N개의 줄에 i번째 논에 우물을 팔 때 드는 비용 Wi가 순서대로 주어짐1 ≤ Wi ≤ 10만다음 N개의 줄에 각 줄에 N개의 수가 들어오는데, i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j를 의미1 ≤ Pi ≤ 10만출력모든 논에 물을 대는데 필요한 최소..

알고리즘 문제) BOJ16946. 벽부수고 이동하기 4문제 요약N*M형태의 맵이 존재0 : 이동할 수 있는 곳1 : 이동할 수 없는 벽한 칸에서 다른 칸으로 이동하려면 인접할 것인접 한다 : 변을 공유할 때이때, 각 벽에대해서 다음을 구하려고함해당 벽을 부순다.그 위치에서 방문할 수 있는 칸의 개수 세기시간 제한2초입력첫째 줄에 N, M이 주어짐1 ≤ N ≤ 10001 ≤ M ≤ 1000N개의 줄에 N개의 숫자로 맵이 주어짐출력맵의 형태로 출력원래 빈칸인 곳은 0, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지로 출력접근법이거는 단순히 벽이 있는 공간에서 bfs를 돌려주면 되지 않을까? 생각하면 시간초과가 뜬다. N과 M이 1000까지 가능하기 때문에그래서 어떻게 푸는게 좋을까 고민하다가,..

알고리즘 문제) BOJ 9344. 도로문제 요약도시 1~N개가 존재이때, 도시 p와 q를 이으면서, 모든 도시를 연결하는 가장 짧은 도로망을 만들 수 있는지 구하기시간 제한2초입력테스트 케이스 개수 T (T≤10)각 테스트 케이스의 첫 줄에는 4개의 정수 N, M, p, q가 주어진다2≤N≤100001≤M≤200001≤p,q≤N이어지는 M개의 줄 각각에는 u, v, w가 주어진다.1 ≤ u ≤ N,1 ≤ v ≤ N,1 ≤ w ≤ 400,000도시 u와 v를 잇는 양방향 길의 비용이 w라는 것을 의미출력각 테스트 케이스에 대해, p-q를 지으면서 가장 짧은 도로망을 만들 수 있으면 YES를 출력한다. 아니면 NO를 출력한다접근법MST 문제 코드import java.io.*;import java.util.*..