본문 바로가기

분류 전체보기94

[백준 Gold 4] 5427 불 - Java 문제링크 : https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 접근 과정 : 단순하게 BFS를 이용한 시뮬레이션이라고 생각했다. 각 테스트 케이스마다 BFS를 이용해서 탈출이 가능한지 시뮬레이션했다. 다만, 다음에 불이 번질 칸으로 이동하지 못하므로 불을 먼저 이동시키고 상근이가 가능한 경로를 탐색했다. 소스 코드 및 결과 : package BOJ; /* 불 */ import java.io.*; import java.util.*; public class BO.. 2022. 1. 1.
[백준 Gold 5] 2589 보물섬 - Java 문제링크 : https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 접근 과정 : 임의의 육지 2개를 고르고, 그 사이의 최단거리가 가장 긴 거리를 탐색하는 문제이다. 육지 하나하나 모두 BFS 해서 최장 거리를 탐색하는 완전탐색 방법으로 풀이할 수 있다. ++ 한 번 거리가 측정된 경로는 다시 탐색하지 않고 사용하는 것이 시간을 줄일 수 있는 포인트.. 이 부분에 대해서는 좀 더 고민이 필요하다. 소스 코드 및 결과 : package BOJ; /* 보물.. 2021. 12. 29.
[백준 Silver 2] 2644 촌수 계산 - Java 문제링크 : https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 접근 과정 : 두 사람간의 촌수를 계산하는데, 두 사람의 공통 조상 중 가장 가까운 공통 조상을 찾아야 한다. 즉, 공통 조상이 여럿 있을 수 있다는 것을 인지해야 한다. (난 이 부분을 인지하지 못해 처음에 실패했다.) 나와 친척의 공통조상은 조부모, 증조 조부모, 고조 조부모가 될 수 있기 때문에!!!! 가장 가까운 공통 조상을 찾아야 한다!! 먼저 입력으로 주.. 2021. 12. 29.
[백준 Gold 4] 1261 알고스팟 - Java 문제링크 : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 접근 과정 : 결국 목적지까지, 벽을 최소한으로 뚫고 가야하는 문제이다. 일반적으로 벽을 뚫은 횟수를 포함한 BFS를 생각했다. 우선순위큐로 벽을 뚫은 횟수가 가장 적은 경우를 꺼내면서 BFS 탐색을 실시했다. 벽을 만났을 때는, 벽을 뚫은 횟수+1 해서 우선순위 큐에 집어넣고, 벽이 아니면 현재 벽을 뚫은 횟수를 집어넣는다. 이렇게 하면 쉽게 해결할 수 있다. .. 2021. 12. 29.

티스토리툴바