백준98 백준 2636번 : 치즈 문제 www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 구현 방법 단계적으로 생각해보았습니다. 1. 치즈 겉 공기 구하기 - (0, 0)은 무조건 빈 칸, (0, 0)부터 인접한 곳이 빈 칸일 때 bfs 돌려 check 배열에 1로 저장. 치즈 속 공기는 1로 둘러쌓여 있기 때문에 치즈 속 공기까지 도달하지 못함. 2. 치즈 속 공기 구하기 - check 배열 값이 0이고 cheese 배열 값이 0이면 치즈 속 공기 -> 2로 변경 3. 사라질 치즈 구하기 - cheese 배열을.. 2021. 3. 24. 백준 16562번 : 친구비 문제 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 구현 방법 union-find 알고리즘을 통해 구현하였습니다. 학생 수 n 만큼의 집합을 만들고 m 만큼의 친구 관계를 통해 친구 관계를 연결해줍니다. 최소 비용을 출력해야하므로 친구 관계 연결 시 루트를 비교해서 가중치가 더 작은 노드를 루트로 올려줍니다. 모두 연결 후 연결되지 않은 친구를 구한 후 가중치를 더해 친구비를 계산해줍니다. 가지고 있는 돈 k .. 2021. 3. 21. 백준 1717번 : 집합의 표현 문제 www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 구현 방법 union-find 알고리즘을 통해 구현하였습니다. n만큼 집합을 생성하고 연산을 받아 0 a b이면 합집합으로 union(a, b) 를 통해 집합을 합쳐줍니다. 1 a b면 연결 되었는지 확인해야합니다. path competition을 통해 연산 시 부모를 루트 노드로 향하게 구현하였으므로 a의 부모, b의 부모를 찾아 같으면 연결 -> "YES" 출력.. 2021. 3. 21. 백준 1976번 : 여행 가자 문제 www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 구현 방법 union-find로 구현해주었습니다. 도시의 수 만큼 root 배열인 parents 배열을 만들어주고 도시 집합을 생성합니다. 연결 정보를 받아와 1이면 union(x, y) 로 집합을 합쳐줍니다. 모든 연결이 끝난 후 여행 계획을 받아와 루트 노드를 찾아 같으면 연결되었으므로 "YES" 출력, 다르면 비연결이므로 "NO"를 출력해줍니다. 구현 코드 package BOJ.Gold; import.. 2021. 3. 21. 이전 1 ··· 9 10 11 12 13 14 15 ··· 25 다음
