본문 바로가기

분류 전체보기94

[백준 Platinum 5] 2618 경찰차 - Java 문제링크 : https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 접근 과정 : DP를 활용하려고 했다. DP를 활용해서 최소 거리를 갱신하는데, 상황별 경찰차의 위치를 어떻게 처리할지가 관건이라고 생각했다. 경찰차의 위치는 사건이 발생한 위치와 같아지므로.. 최근에 각 경찰차가 처리한 사건의 인덱스를 기준으로 DP했다. 그리고 한번 더 탐색하면서, 경로를 저장했다. 소스 코드 및 결과 : package BOJ; /* 경찰차 .. 2022. 1. 4.
[백준 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.

티스토리툴바