자바

[JAVA] 백준 13913 : 숨바꼭질 4

문제 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해결 방법 오랜만에 알고리즘 해설을 준비했는데, 그리 어렵지 않은 문제이다. 어려운 문제는 어떻게 풀어야 할지 아직 감이 잘 안 잡혀서, 문제를 풀더라도 설명을 할 정도로 이해를 하지 못해 가져오지 못했다. 이 문제는 수빈이가 동생을 찾는 숨바꼭질 문제인데, 수빈이는 현재 위치에서 +1, -1 또는 x2 만큼 움직일 수 있고 움직일 때마다 1초씩 소모된다. 즉, 모든 경우의 수를 전부 확인하며 목표지점에 도달하는 시간을 체크..

[JAVA] 백준 16946 : 벽 부수고 이동하기 4

문제 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 해결 방법 어떤 방식으로 해결해야 되는지 몰라 다른 블로그를 참고했다. 참고한 블로그는 이 곳이다 -> https://devowen.com/253 Flood Fill, 즉 플러드 필 알고리즘을 사용해야 한다고 하는데 위 블로그에 자세히 설명되어있다. 문제를 보게되면, 벽과 이동할 수 있는 공간이 존재한다. 벽에 해당하는 부분은 부순다음 해당 칸에서 이동할 수 있는 칸의 개수를 계산해서 벽이었던 1의 해당하는 부분은 해당 칸에서 이동할 수..

[JAVA] 백준 2151 : 거울 설치

문제 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 해결 방법 빛은 일직선으로 나아가고, 45도 각도의 거울을 사용해서 이동방향을 바꿔 목적지에 도착하도록 하는 문제이다. 그래서 현재 방향이 어디인지 저장할 dir을 사용하고, cnt를 사용해서 거울을 몇 번 사용했는지 체크하게끔 class를 구성했다.또 우선순위 큐를 사용해서 가장 거울을 적게 사용한 결괏값이 제일 먼저 목적지에 도착하도록 하였다. 시작점과 도착점이 문제와 같이 2개만 주어지는 문제는 처음 입력을 받을 때 해당 지점을 체크해두고..

[JAVA] 백준 11657 : 타임머신

문제 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 해결 방법 벨만-포드 알고리즘을 사용해야 하는 문제이다. 한 정점에서 다른 모든 정점의 최단 경로를 탐색해야 하는데 Cost가 음인 경우 사용 가능하다. 최단 경로를 나타내는 배열을 최댓값으로 초기화 해준 다음 배열을 사용해서 탐색을 진행한다. 정점의 수 - 1 만큼 반복문을 통해 최단 경로를 탐색해주고, 한 번 더 탐색하였을 때 또 최단 경로가 바뀐다고 하면 음의 사이클이 존재한다는 뜻이다. 여기..

[JAVA] 행렬 테두리 회전하기

문제 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 해결 방법 어려운 문제인가 했는데, 글에 적힌대로 구현하니 작동이 되었다. 그래서 구현은 문제에서 제시한 가로, 세로 크기만큼 배열을 생성한 뒤에 숫자를 입력해주고, 그림의 1, 2, 3, 4번 순서대로 회전하게끔 반복문을 통해 구현했다. 그리고 최솟값을 찾을 수 있게 min 변수를 게속 체크하면서 확인하였다. 1번은 y값을 증가시켜 y2와 일치하면 멈춰주고, 2번은 x값을 증가시켜 x2와 일치하면 멈춰주었다. 3번은 y값을 감소시켜 y1..