https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구해야 한다. 즉, 최댓값을 구해야 하므로 벽 3개를 세울 수 있는 모든 경우의 수를 구해 그 중 안전 영역 크기의 최댓값을 구해야 한다. 문제를 풀기위해 전체 로직을 3단계로 나누었다. 1. 빈 칸 중 3개 선택(DFS/완전탐색) 2. 바이러스 전파(BFS or DFS) 3. 안전영역 크기 세기(이중 for문) 먼저 main 함수에서..
11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 트리라고 해서 트리 구조를 만들어야 하나? 라고 생각할 수도 있는데, 그래프를 그려서 해결할 수 있다. 인접 리스트로 그래프의 정보를 저장하고, 루트 노드에서부터 DFS또는 BFS로 탐색을 시작하여 아직 방문하지 않은 노드를 찾을 때마다 부모 노드 저장 배열(parent)에 부모 노드 번호를 저장하면 된다. 코드 import java.io.*; import java.util.*; public class Main { static int[] parent; //부모 노드 저장 배열 public static void main(S..
13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 사용하여 시작 위치에서 도착 위치까지 가는 최소 시간을 구한다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Str..
https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 구해야 하므로 BFS를 사용한다. BFS 시작 위치는 캐릭터의 시작 위치와 같다. maps는 0과 1로만 이루어져 있으며 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타낸다. 캐릭터의 방문 여부를 나타내기 위해, 캐릭터가 방문한 칸은 maps에서 2 이상의 값으로 나타낸다. 즉, maps[x][y]는 (x, y)좌..
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 맥주 한 박스에는 맥주가 20개 들어있으며 50미터에 한 병씩 마시기 때문에 최대 1000m를 갈 수 있다. 즉, 처음 출발할 때와 편의점에 들렀을 때 최대 1000m를 갈 수 있다. 처음 출발할 때 1000m 이내로 아직 가지 않은 편의점이 있다면 그 편의점으로 가고, 이 과정을 반복해서 페스티벌 장소에 도착할 수 있다면 happy를 출력하고, 갈 수 없다면 sad를 출력하면 된다. ..
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산해야 한다. 비가 내려서 잠기는 높이의 경우의 수마다 BFS를 수행해서 안전한 영역의 최대 개수를 구한다. 로직 1. n을 입력받는다. 2. nxn 크기의 int형 배열 arr을 선언한다. 3. 지역의 높이 정보를 입력받고 arr에 저장한다. 이 때 가장 높은 지점의 높이를 max값에 저장한다. 4. 아무 지점도 잠기지 않으면 안전 영역의 개..
https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 구해야 하므로, BFS를 사용한다. 숫자의 중복 여부를 체크하기 위해 Map을 사용하고, 각 숫자마다 명령어 나열을 저장해야 하므로 Map에 (숫자, 명령어 나열)을 저장한다. 큐에는 숫자를 저장한다. 로직 (시간초과) 1. BFS를 수행할 dslr함수에서 int형 숫자를 저장하는 큐, (숫자, 명령어 나열)을 저장하는 H..
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 처음에는 DFS를 사용하여 S층에서 G층으로 갈 수 있는 모든 경우를 구하고, 그 경우에서 최솟값을 구하려고 하였다. 하지만 시간초과가 떴다. 그래서 구글링을 한 결과 BFS와 방문배열를 사용하여 문제를 풀었다. 층의 방문 여부를 저장하는 방문 배열을 사용하지 않는다면 메모리 초과가 뜬다. 로직 1. BFS를 사용하여 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 구한다. 이 때 한 번 ..