본문 바로가기

Algorithm54

[백준 Gold 2] 17472 다리 만들기 2 - Java 문제링크 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 접근 과정 : 크게 4개의 과정으로 문제를 해결하려고 했다. input() : 입력을 받는 단계. N,M을 입력받고 그에 따라 Map[][] 입력받는다. defindLand() : 섬을 정의하고 구분한다. 섬에 번호를 붙여 구분한다. serarchBridge() : 섬들 사이에 연결할 수 있는 모든 다리를 구한다. minBridges() : 앞서서 구한 다리들을 .. 2022. 1. 4.
[백준 Gold 4] 20040 사이클 게임 - Java 문제링크 : https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 접근 과정 : 분리 집합으로 접근하면 간단하다. 연결 정보에 따라서 집합으로 합쳐주고. 만약 집합의 번호가 같으면 사이클이 형성된다!! 사이클이 형성될 때, i를 리턴한다. +++ 비슷한 문제 : https://rays-space.tistory.com/74 [백준 Gold 4] 4803 트리 - Java 문제링크 : https://www.acmicpc.net/problem/480.. 2022. 1. 3.
[백준 Gold 4] 4803 트리 - Java 문제링크 : https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 접근 과정 : 사이클이 형성되지 않은 트리만을 찾아서 갯수를 세주면 된다. 간선이 연결될 때, 만약 두 정점중 하나가 사이클에 포함되어 있거나, 해당 간선으로 사이클을 형성하게 되는 경우를 확인해야 한다. 트리의 루트 노드를 기억하고, 이를 이용해서 사이클을 확인했다. A,B를 잇는 간선이 있을 때, roo[A] == root[B] 라면 이는 사이클을 형성하게 된다... 2022. 1. 3.
[백준 Silver 3] 9372 상근이의 여행 - Java 문제링크 : https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 접근 과정 : 문제의 접근 방법은 크게 두가지라고 생각한다. 먼저 지나가는 국가를 체크하면서 비행기를 타고, 모든 국가를 다 지나갔을 때, 비행기의 종류를 리턴하는 방법! 그런데 여기에는 약간의 함정이 있다. 국가를 여러번 지나가도 되고, 하나의 비행기를 여러번 타도 된다.!! 즉, 비행기의 종류(간선)이 최소가 되게 모든 국가를 연결하는 것인데 .. 2022. 1. 3.

티스토리툴바