공부공간

https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 입력으로부터 2인 배양가능한 장소를 적절한 부분집합으로 나누어 (DFS) 시간이같은상황에서 서로다른 색깔 (BFS)를 이용하여 판단하는문제 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.A..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진�� www.acmicpc.net 그래프에 간선이 0과 1밖에 없는 경우 특정 시점에서 특정값을 구할때 0-1 BFS를 사용한다. 즉 몇번의 BFS를 통하여 모양이 만들어지는지? 약간말이 이상한데. 위 문제에서는 몇개의 C를 거치면 map의 위치로 갈 수 있는지? 와 치즈가 녹는 시간은 동치이다. 0,0은 치즈가 없음이 보장되어있기에 이쪽에서 bfs를 시작해서 c를 만나면 덱에 뒤쪽에, c를만나지 않으면 덱의 앞쪽에 넣어서 만난 c의개..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 당연히 푼문제인줄 알았었는데 C++로 풀었던문제여서 자바로 다시풀었다. 전체 먹을수있는 상어 후보(?)의 관리는 우선순위큐에관리하여 logN에 찾자. 한스텝마다, 우선순위큐에 먹을수있는 상어들을 뽑고, 그 상어까지의 최단거리 (BFS) 를통하여 처리한후, 그 상어가 있던 자리를 기준으로 다시 힙을 정렬한다. 이 과정을 더이상 먹을수 있는 상어가 없을때까지 진행한다. import java..

https://www.acmicpc.net/problem/2234 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로� www.acmicpc.net 주어진 맵에서 성곽의 크기를 구하면서 벽하나를 제거해서 합친 면적중 가장 큰 값을 찾는 문제이다. 성곽의 크기를 구할때 이미 각 면적의 합을 구하고 인접여부만 CHECK배열로 확인해 준다음 인접해있다면, 두 면적을 합친값 중 가장 큰 값을 답으로 선택한다. 다음 BFS진행시에 비트연산을 해주어야하는 신박한 문제 :) import java.io.BufferedReader; import java.io.Inpu..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 외판원순회(TSP)문제는 한지점에서 출발해 모든 노드를 거치고 다시 시작위치로 돌아오는 문제를 말한다. 그 중 최소 비용을 출력하는 것이 이번 외판원문제2이다. 백트래킹을 이용하여 미리구한값보다 크다면 더이상진행하지않는다. 문제에서도 알수 있듯이, MAP[I][J]값이 0이면..

https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 www.acmicpc.net MAP에서 X를 순서대로 방문한 경로중 가장 짧은 것을 출력하는 문제이다. X의 방문에 순서가 있으므로, NextPermutatio..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출 www.acmicpc.net (1,1)에서 (N,M)이동할때 마검 그람을 얻으면 모든벽을 부수면서 진행할 수있는 문제이다. 벽부수고 이동하기처럼, 방문처..

https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵 www.acmicpc.net 벽을 피해 파이프를 연결하는 문제이다. 파이프는 현재좌표에서 x 좌표는 +1 / y 좌표는 -1,0,1인 지점에 벽이 아닌공간에 설치할 수 ..