Inor

화재가 발생한 빌딩(2차원 배열)에 갇힌 사람을 탈출 시키는 문제 입니다. 불이 옮기는 시점과 사람을 이동시키는 시점을 잘 분류해서 쉽게 해결하였습니다. BFS를 이용해서 사람이 이동 가능한 위치를 찾아서 이동 시키고 화재가 퍼질 수 있는지 확인하여 불이 번지도록 만들었습니다. 사람이 탈출 할 수 있는 최단경로를 찾아야하기 때문에 BFS를 사용 하였습니다. 아래는 문제 링크와 소스 코드 입니다. https://www.acmicpc.net/problem/5427 import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class EscapeFireBuilding ..

안전 영역 문제는 장마철 비가 어느정도 왔을때 안전영역의 갯수가 최대가 되는지 구하는 문제 입니다. 강수량을 확인해서 침수 영역을 만들어주었습니다. 그 후에는 안전구역을 BFS 알고리즘을 사용해서 확인 했습니다. 더 이상 탐색할 곳이 없다면 안전 구역의 번호를 1 증가 시키고 다음 영역을 탐색하였습니다. 처음에는 안전구역이 가장 넓은 경우를 찾는 문제라고 생각했고 비가 가장 조금 왔을 경우에 안전구역이 넓어질 것이라고 생각했습니다. 그러나 안전 구역의 넓이가 아니라 안전 구역이 만들어진 갯수의 최댓값을 구하는 문제인 것을 확인하고 강수량이 될 수 있는 1부터 100까지 모든 경우에서 확인을 하였습니다. 프로그램의 실행 시간을 조금이라도 줄일려면 입력된 구역에서 가장 높은 위치의 값과 강수량을 비교해서 가..

테트로미노 문제는 2차원 배열에 테트리스 게임에서 나오는 막대 모양을 올려 놨을때 해당 위치의 값들을 더해서 최댓값을 찾아내는 문제 입니다. 테트리스에 나오는 막대 모양은 회전, 대칭이 가능하다고 문제에서 설명해주고 있습니다. 해당 문제는 DFS를 이용해서 풀었습니다. 모든 막대기를 만드는 블록들이 총 4개라는 공통점을 찾았고 4번씩 이동했을때 모든 테트리스의 막대기 모양이 만들어진다는 것을 직접 그려가며 발견하였습니다. 4번 이동했을 경우에 1번, 2번, 3번, 4번째에 탐색된 위치의 값들을 더해서 최댓값과 비교하였습니다. 그러나 여기서 한가지 예외 상황이 있었는데 ㅗ모양의 막대기는 DFS를 이용해서 해결할 수 없다는 문제를 발견하였습니다. 이유는 중간에 3갈래 길이 생기는데 재귀함수를 이용해서 모든 ..

2차원 배열에 위치한 토마토가 4방향(동, 서, 남, 북)으로 퍼지면서 주변에 토마토들이 익어가는 문제 입니다. 전형적인 BFS 문제이라고 판단하였고 BFS를 이용해서 문제를 해결하였습니다. 초기에 입력된 정보에서 토마토의 위치를 큐에 넣어두고 BFS탐색을 시작하였습니다. 토마토가 이미 익었을 경우와 벽이 있는 경우에는 큐에 넣지 않았고 익지 않은 토마토를 큐에 넣고 현재 위치의 토마토가 익은 날짜 +1을 해서 몇일째에 토마토가 익었는지 2차원 배열에 표시하였습니다. 아래는 문제와 소스 코드 입니다. https://www.acmicpc.net/problem/7576 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

연구소에 바이러스가 퍼지지 못하게 3개의 기둥을 세워서 피해를 최소한으로 만드는 알고리즘 문제 입니다. 탐색(BFS, DFS)에대해서 공부해야겠다는 생각을 갖도록 만들었던 문제 입니다. 처음에는 어떻게 접근해야할지 감도 못잡았는데 탐색에대해 공부하니 어렵지 않게 풀 수 있었습니다. 아래는 문제의 링크 입니다. https://www.acmicpc.net/problem/14502 3개의 기둥을 세우는 방법은 재귀 함수를 만들어서 해결 했습니다. 3개의 기둥이 모두 세워졌을때 BFS탐색을 이용해서 벽이 아닌 곳으로 바이러스를 퍼뜨렸습니다. 그리고 바이러스가 퍼진 연구소를 다시 원상 복귀 시키며 바이러스가 퍼지지 않은 부분을 계산하였습니다. 문제를 풀면서 아쉬웠던 부분은 기둥을 세우는 부분의 재귀 함수를 조금 ..

로봇 청소기를 회전 시키며 이동시키고 이동한 구역을 청소하는 방식으로 프로그램이 실행되도록 하는 알고리즘 문제 입니다. 저는 DFS를 이용해서 로봇청소기를 이동 시키려고 했습니다. 그러나 코드를 다 만들고나서 들었던 생각은 이건 DFS는 아니고 그냥 단순히 시뮬레이션으로 만든것 같다는 느낌이 들었습니다. DFS를 사용하려고 했다는 것에 큰 의미를 두겠습니다.. 아래는 문제의 링크 입니다. https://www.acmicpc.net/problem/14503 구현 과정에서 가장 먼저 생각했던 것은 로봇청소기를 회전 시키는 방법과 청소할 구역이 없을때 후진 시키는 방법을 생각하였습니다. 회전의 경우에는 지금 로봇이 바라보고 있는 위치의 값에 따라서 변경해주었습니다. 후진도 마찬가지로 현재 바라보는 방향에서 뒤..