문제 지훈이가 불에 타기 전에 미로를 탈출할 수 있으면 탈출 시간을 출력하고 불가능하다면 IMPOSSIBE을 출력하는 문제로 불은 매시간 상하좌우 4방향으로 한 칸씩 확산되고 지훈이는 상하좌우 한 칸씩 이동할 수 있다. (지훈이와 불은 모두 벽을 통과할 수는 없다) 접근 방식 지훈이와 불을 동시에 출발시켜서 지훈이가 미로를 탈출하는지를 확인하면 되는 문제로 접근 방식을 떠올리는 건 간단한 문제다. 이제 어떻게 동시에 출발 시키냐는건데 일단 반복문에서 동시에 불과 지훈이를 한 번에 같이 탐색하는 건 불가능하다. (추후에 백트래킹을 배우면 가능하다.) 그래서 불과 지훈이를 각각 따로 움직여서 기록을 남길 건데, 이전에 풀어왔던 BFS 문제들처럼 거리를 남겨주면 된다. 불들의 거리를 모두 남긴 이후에 지훈이를..
Java
문제 상자에 익은 토마토와 덜 익은 토마토, 빈 공간이 존재할 때 익은 토마토의 주변 한 칸 내에 있는 덜 익은 토마토들은 하루가 지날 때마다 영향을 받아 익는다. 이때 상자 안에 존재하는 모든 토마토가 익기 위해서는 최소 며칠이 걸리는지 출력하라. (모두 익을 수 없는 경우에는 -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의 제곱, (..
문제 주어진 쇠막대기들에 레이저를 발사했을 때 쇠막대기가 총 몇 개로 나뉘는지 계산하는 문제 접근 방식 풀고 나니 엄청 간단했지만 풀이법을 알기까지 많은 시간이 걸린 문제로 코드를 보면 알겠지만 엄청 간단한 문제다. ()(((()())(())()))(()) 위와 같은 문자열이 주어졌을 때 괄호가 열리자마자 닫히면 레이저고 그렇지 않다면 쇠막대기라는 것을 알 수 있다. 쇠막대기의 양끝과 레이저는 겹치지 않기 때문에 쇠막대기 위에 레이저가 발사되면 무조건 쇠막대기가 잘라진다. 즉 레이저를 쐈을 때 현재 스택에 있는 쇠막대기의 수만큼 쇠막대기가 늘어나기 때문에 열리자마자 닫히는 괄호를 발견했을 때마다 스택의 사이즈만큼 더해주면 된다. 주의해야 할 점은 쇠막대기가 끝날 때도 1씩 더해줘야 하는데 길이가 3인 쇠..
문제 A와 B로만 이루어진 문자열이 주어졌을 때 같은 글자끼리 선을 그어 교차하지 않고 모두 맞아떨어지는 경우 주어진 문자열을 좋은 단어라고 판단하고 좋은 단어가 몇개인지 출력하는 문제 접근 방식 좋은 단어에 대한 설명이 헷갈릴 수 있는데 아래와 같다. AABB (O) ABBA (O) ABAB (X) 알 수 있는 사실은 연속해서 존재하거나 중간에 다른 단어의 선과 겹치면 안 된다는 건데 같은 경우 빼주고 같지 않은 경우는 넣어주면 되므로 스택을 사용하면 쉽게 풀 수 있다. ABBA 같은 경우만 신경 써서 풀면 되는 문제로 아래와 같은 순서로 실행되는 코드를 짜면 된다. Stack stack = new Stack(); // ABBA stack.push('A');// stack(A) peek() == 'B'..