https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색, 시뮬레이션 설명 외부 공기와 접촉하는 칸이 두 곳 이상이면 치즈가 녹습니다. 이때, 모든 치즈가 녹으려면 얼마만큼의 시간이 필요한지 구하는 문제입니다. DFS, BFS 중 어느것을 사용해도 무방하나, 저는 DFS를 사용하여 풀이하였기에, 본 포스팅에선 DFS를 사용한 접근법과 풀이를 서..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 트리, 재귀 설명 입력으로 pre order(전위 순회)가 주어지고, 이를 트리 형태로 변환하여 post order(후위 순회)하여 방문한 노드 순서대로 출력하는 문제입니다. 소스코드 전체 소스코드 import java.io.BufferedReader import java.io.InputStreamReader val sb = S..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 벨만-포드 설명 1번 도시에서 출발해 나머지 도시로 가는 최단경로를 구하는 문제입니다. 다만, 음의 간선이 존재하므로 다익스트라는 사용하기 어렵습니다. 음의 간선이 있다는 것을 보고, 어떻게 풀어야하나... 하며 최단경로 알고리즘을 찾아보다가, 음의 간선일때의 쓰는 최단경로 알고리즘인 벨만-포드..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 탐색, 그래프 이론, 다이나믹 프로그래밍 설명 DFS를 사용하여, 직전 파이프의 형태 (가로, 세로, 대각선)을 참고하여 풀이할 수 있는 문제입니다. 처음엔 DFS 없이 DP만을 사용하여 풀이하려고 했으나, 생각보다 잘 되지 않아서, 마침내 그래프 탐색 문제인걸 깨닫고 푼 문제였습니다. 소스코드 전체 소스코드 import java.io...

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 데이크스트라, 플로이드-워셜 설명 각 정점에서 m 만큼의 비용 안에 갈 수 있는 정점들의 아이템 값의 최대값을 구하는 문제입니다. 한 정점과 연결된 다른 정점을 순차적으로 탐색하는 방식으로 DFS, 다익스트라 알고리즘을 사용해 풀이할 수도 있지만, 본 포스팅에서는 플로이드 - 워셜 알고리즘을 사용하여 풀이하겠습니다. 소스코드 인풋값 세팅 val MAX_VALU..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 이전에 많이 해보았던 상하좌우 4방향으로 이동하는 BFS 문제에, 체스의 나이트 방향으로 움직일 수 있는 조건이 더해진 문제입니다. 단, 나이트 이동의 경우 k번이라는 제약조건이 있으므로, 말 이동을 k번 이하로 사용하면서 최단 경로로 목표지점에 도달하는게 핵심입니다. 소스코드 Data Class - P..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 난이도 : 골드4 태그 : 자료구조, 그래프 이론, 그래프 탐색, 분리 집합 설명 파티에 진실을 아는 사람이 포함되어 있으면, 그 파티에 참여한 사람들은 모두 진실을 알고 있다고 간주하고, 진실을 알고 있는 사람들이 하나도 포함되어 있지 않는 파티를 카운트하는 문제입니다. 문제 태그에도 명시되어 있듯이 그래프 탐색(DFS/BFS)를 통해서도 풀 수 있지만, 분리 집합 (Union - Find 알고리즘 이용)..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 난이도 : 골드3 태그 : 그래프 이론, 위상정렬 설명 누가 누구보다 더 앞선 우선순위를 갖고 있다는 사실만으로 정렬을 하는 위상정렬 문제입니다. 예를 들어 A, B, C, D, E. 5명의 사람을 키 순서대로 정렬하려 할때, 170cm, 180cm, 190cm, 160cm, 150cm 등으로 각 사람의 키가 주어지면 손쉽게 정렬 할 수 있겠지만, A는 B보다 작다. D, E는..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 백트래킹, 깊이 우선 탐색 설명 DFS를 사용한 백트래킹을 사용하여 풀 수 있는 문제 입니다. 아이디어 자체는 빨리 떠올랐는데, 시간초과 때문에 꽤 애먹었던 문제였습니다. 처음엔 방문한 좌표와 사용한 알파벳을 각각 체크하였는데, 생각해보니 사용한 알파벳만 체크해도 되더군요. 사용한 알파벳 역시 ArrayList로 했더니 시간초과가 나..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프이론, 플로이드 - 워셜 설명 문제의 제목처럼 플로이드 - 워셜 알고리즘을 이용해 해결할 수 있는 문제입니다. 플로이드 - 워셜 알고리즘의 기본격인 문제이니, 해당 알고리즘을 알고 계신다면 어렵지 않게 풀 수 있습니다. 저는 잘 몰라서 플로이드 - 워셜 알고리즘이 뭔지 찾아보고서야 풀었네요...ㅎㅎ 소스코드 값 입력과 테이블 준비 val br = BufferedR..