[백준 / BOJ] 14466 소가 길을 건너간 이유 6 (Java)
문제 출처 : https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net N*N그리드에 K마리의 소가있고, R개의 길이있다. 각 소들이 상하좌우로 움직일수있을때, 길을 건너지않고 만날수없는 소들의 쌍을 구하는 문제다. 풀이 알고리즘 보다는, 문제 해석과 적절한 자료구조를 생각해 내는게 핵심인 문제였다. 처음에 문제를 봤을때 문제가 무엇을 원하는지 파악을 못했는데, 문제를 쉽게 축약해보면, "길을 지나가지않고는 서..
[백준 / BOJ] 17780 새로운 게임 (Java)
문제 출처 : https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net (...) 풀이 문제에서 주어진 그대로 풀면되는 시뮬레이션 문제였다. 문제 해석시 주의할점이 있었는데, 1. 다음 위치가 빨간색인데, 이동할 위치에 이미 다른 체스말들이 있는경우, 이동후 체스말을 위로 쌓은다음에 체스말의 순서를 뒤집는것이 아니라, 이동 전에 뒤집고 체스말을 위로 쌓는것이다. 예를들어, 현재 이동할 체스말들이 (1,2,3) 순서대로 쌓여있고 이동위치에 이미 (4,5)..
[백준 / BOJ] 10021 Watering the Fields (Java)
문제 출처 : https://www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 농부 존은 자신의 지역에 물을보내주는 시스템을 만들려고한다. 이때, 각 지역을 연결하는 비용..
[백준 / BOJ] 4883 삼각 그래프 (Java)
문제 출처 : https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net N(N>=2)개의 행, 3개의 열로이루어진 삼각그래프 가있다. 삼각그래프의 각 노드는, (y,x일때) 자신의 위치기준으로 (0, -1) (-1, -1) (-1, 0) (-1, 1)위치에 있는 노드들에서 올수있다. (해당 위치에 노드가 없는경우 올수없다.) 각 노드에 가중치가 있을때, (1,2)위치부터 (N,2)위치까지 가는 최소경로를 구하는 문제다. 풀이 다이나믹 프..
[백준 / BOJ] 1445 일요일 아침의 데이트 (Java)
문제 출처 : https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 형택이는 여자친구와 데이트를 하려고한다. 자신의 여자친구는 쓰레기를 지나가는것과, 쓰레기 주위를 지나가는것을 굉장히 싫어하기 때문에, 형택이는 이러한 상황을 최대한 피하고자한다. 숲의 크기 n,m 쓰레기의 위치(g), 형택이의 위치(S), 도착위치(F)가 주어진다. 이때, 위와 같은 상황을 최소화 하여 움직였을때 쓰레기를 지나간 횟수와 쓰레기 주위를 지나..
