문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 주어진 도로와 도시 정보에서 모든 도시간의 거리가 1이라는 점을 이용해 너비 우선 탐색(BFS)으로 해결할 수 있다. 시작 도시로부터 BFS를 수행하며 거리를 계산하고 거리 배열에 저장해준다. 여기서 모든 도시간의 거리가 1이기 때문에 도시에 처음 도착했을 때의 거리가 최단 거리일 것이다. 탐색이 끝난 후 찾으려는 거리에 도시가 있다면 도시를 출력해주고, 없다면 -1을 출력한다. ..

문제 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 BFS를 활용해 풀이하면 된다. 먼저 입력을 받고 치즈의 총량을 확인해준다. while문 반복을 통해 치즈가 없어 질 때까지 BFS 함수를 실행한다. 공기와 접촉되어 있는 치즈를 확인하기 위해 Queue에 공기를 담아가며 탐색하고 치즈를 만나면 체크해준다. BFS 탐색이 끝나면 체크되어 있는 치즈를 녹여주고 치즈의 총랑에서 빼준다. 모든 치즈가 녹으면 반복문을 종료하고 시간와 마지막으로 남은 치즈를 출력해준다. 코드 import java.util.* data class ..

문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 토마토가 익는 과정은 동시에 일어나기 때문에 Queue를 이용한 BFS(너비 우선 탐색)으로 해결할 수 있다. 배열을 입력 받아 익은 토마토(1)인 경우에는 Queue에 추가해준다. 익지 않은 토마토(0)인 경우에는 익지 않은 토마토의 개수를 확인하는 변수인 cnt를 증가시켜준다. 이제 BFS를 실행하면 된다. 큐에서 하나의 위치를 꺼내어 상하좌우를 탐색하며 익지 않은 토마토(0)를 만나게 되면 cnt를 1 감소시키고 배열에 현재 날짜..

문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 각각의 테스트 케이스마다 입력받은 graph를 DFS, BFS로 탐색한 결과를 출력해주면 된다. graph는 false로 초기화되어 있는 BooleanArray를 선언한다. 입력받은 좌표는 true로 바꿔준다. for문을 통해 graph의 좌표가 true이면 DFS, BFS 함수를 실행해주고 cnt를 +1 해준다. 이후 cnt를 출력해주면 된다. 코드 - BFS import java.util.* data class Point(val x: Int, val y: In..

문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 풀이 이러한 문제들의 graph는 2차원 ArrayList로 만들 수 있다. 연결되어 있는 컴퓨터 번호 쌍을 각각의 ArrayList에 추가해준다. 1번 컴퓨터와 연결되어있는 컴퓨터들을 찾는 문제로 1번 컴퓨터부터 시작하는 BFS와 DFS로 해결하는 문제이다. BFS로 해결하는 경우 Queue를 이용한다. 큐에서 꺼낸 ArrayList에 연결되어있는 번호가 방문한 적이 없다면, 그 번호로 시작하는 ArrayList를 queue에 추가해주고 cnt는 +1 해준다...