Jutudy

https://www.acmicpc.net/problem/15686 풀이 0 2 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 2 위의 예제를 보자. 집의 개수 : 6개 치킨집(가게)의 개수 : 2개 각각의 집은 치킨거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합니다. 각 집에서 모든 치킨집까지의 최단 거리를 각각 구할 수 있다. 이 중 가장 가까운 곳에 있는 치킨집까지의 거리가 해당 집의 치킨거리가 되는 것이다. 위의 예제에서 (0,1)의 집에서부터 한 번의 BFS(DFS도 가능)을 수행하면 모든 치킨집까지의 최단 거리를 구할 수 있다. 이런 식으로 각 집의 위치를 시작점으로 BFS를 수행(집의 개수만큼 BFS수행)하게되면, 모든 집에서부터 모든 치킨..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] 수빈이의 현재 점에서부터 BFS를 시작한다. 갈 수 있는 경우는 (X-1, X+1, 2*X) 3가지 경우이다. 가장 빠른 시간을 찾는 문제이기 때문에 이미 방문한 위치를 또 방문하는 경우에는 다시 큐에 넣지 않는다. [소스코드] import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOExce..

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net [풀이] ​ BFS 문제이다. ​ 바깥 부분이 공기이기 때문에 바깥 부분에서 BFS를 진행하면 공기와 맞닿은 치즈를 찾을 수 있다. ​ 공기와 맞닿은 치즈 부분을 찾은 뒤 그 부분을 공기로 바꾸고 바뀐 치즈의 개수를 카운트하면서 치즈가 남지 않을 때 까지 반복하면 된다. ​ 공기(0,0)에서 BFS 진행 공기 공기 공기 공기 공기 공기 치즈 치즈 치즈 공기 공기 치즈 빈칸 치즈 공기 공기 치즈 치즈 치즈 공기 공기 ..

https://www.acmicpc.net/problem/16959 16959번: 체스판 여행 1 크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다. 지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다. 지학이가 가지고 있는 말은 나이트, www.acmicpc.net [풀이] ​ BFS 문제이다. ​ 말은 1에서 시작해서 N^2-1 까지 차례대로 밟아가며 이동해야한다. ​ 차례대로 숫자가 1씩 늘어나면서 방문해야 하기 때문에 말은 현재 자신이 방문한 숫자 정보를 가지고 있어야 한다. ​ 중간에 다른 숫자가 적혀있는 부분도 거쳐갈 수 있기 때문에 자신이 다음에 방문해야 할 숫자가 아니면 원래 말이 가지고 있던 숫자 정보를 그대로 가지고 간다. ​ 현재 ..