Algorithm

[JAVA] 백준 8972 : 미친 아두이노

문제 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 해결 방법 다 풀고 나서 보니 BFS 방법을 이용해서 푸신 분들도 있었다. 그 분들에 비하면 내 코드가 속도가 느리긴 하지만, 이런 코드도 있다 정도로 봐주면 좋겠다. 문제의 1~5번을 순서대로 구현했고, 방향은 dx, dy 배열을 통해 입력해두었다. 입력의 젤 마지막에 종수가 움직이는 방향이 주어지는데, 주어질 때마다 moveI 함수를 실행시켜 전체 맵을 변경시켜주었다. moveI 함수는 처음에 입력받은 값에 따라 종수 아두이노를 움직이고, 종수 아두이..

[JAVA] 백준 11967 : 불켜기

문제 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 해결 방법 루모스 ~ 기본적인 탐색 문제에서 불을 켜고, 불이 켜진 방만 이동이 가능한 조금 응용된 문제이다. 각 방에 있는 스위치를 나타내기 위해서 ArrayList 배열을 사용해서 리스트에 불을 켤 수 있는 곳의 좌표를 넣어 두었고, light와 visit을 활용해서 불이 켜져 있는지 여부와 방문 여부를 체크하였다. 탐색은 BFS를 사용했는데 불을 켤 수 있는 방이 존재하는지 여부는 리스트가 비었는지 ..

[JAVA] 백준 13335 : 트럭

문제 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 해결 방법 처음엔 큐를 사용해서 구현을 하려다가 그냥 리스트로 구현을 해도 무관해보여서 리스트로 구현을 했다. Truck 클래스를 통해서 무게와 다리에 머문 시간 값을 가질 수 있게 해주었고, 다리에서 머문 시간이 w와 동일하면 리스트에서 제거해주는 방식을 사용했다. 리스트에서 값을 제거하면 index 값이 한 칸씩 앞으로 당겨지기 때문에 i--를 통해서 맞추어주었고, 다음 순서의 트럭이 어떤 트럭인지 알기위해..

[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..