Java/Algorithms

문제 배추 밭에 배추가 있는 곳과 없는 곳이 존재할 때 배추흰지렁이가 몇 마리 있어야 배추가 존재하는 곳에 해충이 들지 않게 할 수 있는지 구하라 배추흰지렁이가 있는 배추가 하나라도 존재하면 지렁이는 상하좌우 한 칸 이내에 인접한 배추로 옮겨 다닐 수 있다. 접근 방식 서로 끊어지지 않고 이어져 있는 배추라면 지렁이가 모두 해충을 처리할 수 있기 때문에 서로 이어진 배추들이 총 몇 개인지 확인하면 된다. 즉 서로 인접하지 않은 출발점들이 몇 개인지 확인하면 되는 문제로 이전에 풀었던 1926번 그림 문제와 같은 방식으로 풀 수 있다. 풀이 public class Main { private static StringTokenizer st; private static int m; private static i..

문제 수빈이의 위치와 동생의 위치가 주어졌을 때 수빈이가 동생을 찾기까지 걸리는 가장 빠른 시간을 구하는 문제 수빈이는 1초마다 좌우로 한 칸 이동하거나 순간 이동하여 현재 위치 * 2만큼 이동할 수 있다. 접근 방식 DFS 혹은 BFS를 이용해서 풀 수 있는 문제로 BFS로 풀어보겠다. 기존에 풀던 BFS 문제와는 다르게 2차원 배열이 주어지지 않았는데 2차원 배열에서는 현재 위치에서 상하좌우로 탐색을 했다면 이번에는 현재 위치에서 좌우로 한 칸 혹은 현재 위치 * 2만큼 이동하면서 탐색하면 된다. BFS에서 큐는 먼저 방문한 순서대로 정렬되기 때문에 동생의 위치에 처음 방문했을 때 시간을 기록하고 반복문을 종료하면 가장 빠르게 방문할 수 있는 시간을 알 수 있다. 풀이 public class Main..

문제 지훈이가 불에 타기 전에 미로를 탈출할 수 있으면 탈출 시간을 출력하고 불가능하다면 IMPOSSIBE을 출력하는 문제로 불은 매시간 상하좌우 4방향으로 한 칸씩 확산되고 지훈이는 상하좌우 한 칸씩 이동할 수 있다. (지훈이와 불은 모두 벽을 통과할 수는 없다) 접근 방식 지훈이와 불을 동시에 출발시켜서 지훈이가 미로를 탈출하는지를 확인하면 되는 문제로 접근 방식을 떠올리는 건 간단한 문제다. 이제 어떻게 동시에 출발 시키냐는건데 일단 반복문에서 동시에 불과 지훈이를 한 번에 같이 탐색하는 건 불가능하다. (추후에 백트래킹을 배우면 가능하다.) 그래서 불과 지훈이를 각각 따로 움직여서 기록을 남길 건데, 이전에 풀어왔던 BFS 문제들처럼 거리를 남겨주면 된다. 불들의 거리를 모두 남긴 이후에 지훈이를..

문제 상자에 익은 토마토와 덜 익은 토마토, 빈 공간이 존재할 때 익은 토마토의 주변 한 칸 내에 있는 덜 익은 토마토들은 하루가 지날 때마다 영향을 받아 익는다. 이때 상자 안에 존재하는 모든 토마토가 익기 위해서는 최소 며칠이 걸리는지 출력하라. (모두 익을 수 없는 경우에는 -1) 접근 방식 익은 토마토가 여러 곳에 존재하는 경우에는 각각의 익은 토마토에서 매일 상하좌우 칸의 덜 익은 토마토를 1로 바꿔줘야 한다. 이전에 풀었던 최단 거리 문제와 비슷한 방식으로 풀 수 있는 문제지만 출발지가 여러 개라는 조건이 추가된 문제다. 1926번 + 2176번 문제가 합쳐진 경우로 모든 출발지를 찾은 후에 큐에 넣고 BFS 알고리즘을 적용하면서 상하좌우에 거리를 1씩 늘려주면 된다. 이번 문제에서 거리는 날..

문제 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 위와 같은 미로가 주어졌을 때 도착지까지 갈 수 있는 최단 경로를 구하는 문제 접근 방식 기존 BFS 알고리즘으로 문제를 풀 때는 방문 여부만 기록했다면 이제는 방문 여부와 출발지로부터의 거리도 기록해주면 된다. 1 0 9 10 11 12 2 0 8 0 12 0 3 0 7 0 13 14 4 5 6 0 14 15 도착지를 처음 방문 했을 때가 가장 빠른 최단 경로일테니 출발지에서 도착지까지의 거리를 출력해주면 된다. 조심해야 할건 같은 지점에서 갈 수 있는 경로의 거리는 서로 같아야 한다. 1 0 9 10 11 13 2 0 8 0 14 0 3 0 7 0 15 16 4 5 6 0 17 18 이런식으로 되면 잘못된 결과..

알고리즘 설명 가장 간단하게 설명하면 출발지에서 가까운 곳부터 방문하는 알고리즘으로 주로 최단 경로를 구할 때 많이 사용된다. static int[][] board = { {1, 1, 1, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {1, 1, 1, 0, 1, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} }; 위와 같은 2차원 배열이 주어졌을 때, 현재 위치에서 자신의 상하좌우 칸을 큐에 넣어주어 가까운 순서대로 반복하며 탐색하는 방법을 사용한..

문제 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 위와 같은 입력이 주어졌을 때 그림의 개수와 가장 큰 그림의 사이즈를 출력하는 문제 접근 방식 위의 입력에서는 총 4개의 그림이 있고 가장 큰 그림의 사이즈는 9라는 것을 알 수 있다. 눈으로 보면 당연한 거지만 이를 코드로 구현하는 것이 BFS를 처음 배우고 푸는 문제라서 많이 어려웠다... 우선 입력 받은 값들을 그림 배열에 저장해 준 후에 해당 그림 배열을 돌면서 찾아주면 된다. 이때 방문한 배열을 다시 방문하지 않기 위해 0이나 1 혹은 true false로 방문 여부를 저장할 배열을 만들어 기록해 준다. Queue Q = new LinkedList(); isVisited[0][0] =..

문제 () = 2, [] = 3 이고 (x) = 2 * x, [x] = 3 * x 일 때 괄호로만 이루어진 문자열의 계산 결과를 구하는 문제 (잘못된 괄호인 경우에는 무조건 0을 출력) 접근 방식 문제의 이해는 쉽지만 구현이 어려웠던 문제다. (()[[]])([]) ( (( (() (2 (2[ (2+[[ (2+[[] (2+[3 (2+[3] (2+9 (11 (11) 22 22+( 22+([ 22+([] 22+(3 22+(3) 22+6 28 주어진 문자열에 대한 계산 순서는 위와 같은데 문제를 자세히 읽어 보면 잘못된 괄호의 경우에는 생각할 필요가 없고 제대로 된 괄호의 경우만 생각하면 된다. 즉, 모든 괄호가 알맞게 짝지어져 있다는 가정 하에 계산을 하면 되는데 () = 2니까 (()) = 2의 제곱, (..