BFS
[JAVA] 백준 4991 : 로봇 청소기
문제 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 해결 방법 처음엔 우선순위큐를 활용한 BFS로 거리를 계산해서 최소 거리를 알아내면 될 것 같아서 시도해보았는데, 최소 거리로 움직이면서 다음으로 탐색하는게 전체적으로 더러운 칸을 모두 제거하였을 때 최소 거리가 아닐 수도 있다고 한다. 그래서 처음에 짠 코드는 실패하였다. 해결한 방법은 다음과 같다. 먼저 로봇과 각 더러운 칸들 간의 거리를 정리할 배열을 생성해두고 값을 넣어주어야한다. BFS 탐색을 활용해서 로봇에서 더러운 칸의 거리들, 더러운 칸들과 더러운 칸..
[JAVA] 백준 6087 : 레이저 통신
문제 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 해결 방법 C에서 C로 길을 찾는데 방향을 바꾸기 위해서는 거울을 사용한다. 사용할 거울을 최소로 하는 길을 찾는 문제이다. 보자마자 우선순위 큐를 활용해서 최단 거리를 구하면 되지 않을까 생각하고 구현해보았다. 중간에 visit 배열의 조건을 부여하는 부분에서 제가 짠 코드보다 아래 블로그의 코드가 쉽고 보기 좋아서 참고해서 수정하였다. 참고한 블로그 -> velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%806087..
[JAVA] 백준 2638 : 치즈
문제 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 해결 방법 하루가 지나면 녹는 치즈들이 며칠 후에 완전히 녹는지 알아내는 문제다. 외부 공기와 접촉한 부분이 2부분 이상이면 녹게 되는데, 치즈로 둘러쌓여 있는 부분이면 외부 공기에 해당하지 않는다. 문제에서 가장자리들에는 치즈가 놓이지 않는다고 하였기 때문에 초기에 0, 0 에서 탐색을 시작해서 탐색이 가능한 부분이 외부 공기에 해당하는 부분이라고 생각하면 된다. 외부 공기에 해당하는 부분은 3으로 초기화를 해준다음에 치즈의 상하좌우에 3인 부분..
[JAVA] 백준 1261 : 알고스팟
문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 해결 방법 다익스트라 알고리즘을 사용해서 풀어야 합니다. 다익스트라 알고리즘은 A에서 B로 가는 것의 최단 거리를 구할 때 주로 사용합니다. 이 문제에서는 시작 지점과 끝 지점이 지정되어있고, 구해야 하는 벽을 부순 횟수가 음수로 존재하지 않기 때문에 사용이 가능합니다. 코드는 다익스트라 알고리즘을 그대로 구현한 것이라 따로 설명하진 않겠습니다. 아래 링크의 분이 잘 설명해두셔서 참조 남깁니다. [알고리즘/자바] 다익스트라 알고리즘 (..
[JAVA] 백준 2933 : 미네랄, 18500 : 미네랄2
문제 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 미네랄 2도 같은 코드로 해결 가능. 해결 방법 범위는 크지 않아서 문제에서 주어진대로 구현만 하면 된다. 처음에 문제가 이해가 잘 되지 않아서 내가 이해한 것을 바탕으로 최대한 풀어서 설명하려고 한다. 일단 문제에서 얘기하는 클러스터는..