Problem Solving/BOJ
-
[BOJ] #6086 _ 최대 유량Problem Solving/BOJ 2020. 3. 9. 01:43
[최대 유량] https://www.acmicpc.net/problem/6086 6086번: 최대 유량 문제 농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다. 두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다. +---5---+ www.acmicpc.net 네트워크 플로우 문제이다. 해당 문제는 양방항 그래프라는 점을 유의해서 풀어야 한다. [ Ford-Fulkerson Al..
-
[BOJ] #7616 _ 교실로 가는 길Problem Solving/BOJ 2020. 3. 9. 01:15
[교실로 가는 길] https://www.acmicpc.net/problem/7616 7616번: 교실로 가는 길 문제 상근이네 반에는 총 K명의 학생이 있다. 그 중 일부는 서로를 엄청나게 싫어한다. 서로 싫어하는 친구는 교실 밖에서 절대 마주치지 않는 경로를 이용해 교실로 이동하려고 한다. 이런 경로를 찾아보자. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 찾아야하는 경로의 수 K와 교차로의 수 N이 주어진다. 교차로는 1번부터 N번까지 번호가 매겨져 있다. 다음 N개 줄에는 각 교차로가 어떤 교차로와 연결되어 있는지 주 www.acmicpc.net 네트워크 플로우를 이용할 수 있다. 단, 교차로에서 친구를 마주치면 안되기 때문에 정점의 중복 방문을 제외시켜..
-
[BOJ] #17472 _ 다리 만들기 2Problem Solving/BOJ 2019. 10. 22. 22:58
[다리 만들기 2] https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net map의 정보를 0과 1로만 준다. 따라서, 바다를 각 숫자로 만들어주고, 최단 거리를 구한 후, 모두 연결되어 있는지 확인하였다. getNewMap() 함수를 통해 아래와 같이 바다를 각 숫자로 변경해주었다. getDistMap() 함수를 통해 각 바다의 거리를 구해주었다. 최단거리를 구하고, 모두 연결되어 있는지 확인하기 위해 크루스칼 알고리즘을 사용하..
-
[BOJ] #17471 _ 게리맨더링Problem Solving/BOJ 2019. 10. 22. 22:13
[게리맨더링] https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 두 구역으로 나눌 수 있는 모든 경우의 수를 고려하여 인구 차이의 최솟값을 구하는 문제이다. next_permutation을 통해 구현하였다. 알고리즘의 흐름은 다음과 같다. 1. 경우의 수 만들기 (1:N, 2:N-2 ...) 2. 각 구역의 연결 유무 확인 3. 두 구역 모두 연결되어 있다면, 인구 수 차이 구하기 checkConnection()의 매개변수인 type은 1구역 2구역을 나타내는 변수이..
-
[BOJ] #17281 _ 야구Problem Solving/BOJ 2019. 10. 22. 20:31
[야구] https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 www.acmicpc.net 야구의 룰을 알면 쉽게 이해할 수 있다. 야구의 룰을 그대로 시뮬레이션하여 구현하는 문제이다. 처음에는 vector를 사용하여 뒤에..