개발하는 고라니

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net [플로이드-와샬 (Floyd-Warshall) 알고리즘] 이 문제를 풀기위해 플로이드 와샬 알고리즘을 공부했다. 이 문제를 DFS만으로 풀려고 하니까 TC에서 헤어나오질 못하였다. 사실 당연하다. 최대 정점의 수는 500개이나, 이후 최대 50,000개의 사건이 주어지므로, DFS 1번 당 최대 50,000 재귀를 한다고 할 때, 25,000,000번 호출되지 않을까? 하는 생각이 들었다. 역시 어떻게 풀어야할지 몰라 무식하게 접근한 꼴이다. 플로이드 와..

그래프가 주어졌을 때 하나의 시작 정점에서 다른 모든 정점들로 가는 최단 경로를 구하는 알고리즘은 다익스트라(Dijkstra)와 벨만-포드(Bellman-Ford)가 있다. 만약 그래프에 존재하는 모든 정점 사이의 최단 경로를 구하려면 다익스트라 알고리즘을 정점의 수(n) 만큼 반복 실행하면 된다. 즉 구해야할 최단 경로가 총 n^2개다. (자기 자신으로의 경로 포함) 하지만 이보다 간단한 방법으로 모든 정점 쌍 사이의 최단 경로를 구하는 방법인 플로이드-와샬(Floyd-Warshall) 알고리즘을 알아보고자 한다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택했다면, 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다. 또한 이 알고리즘은 동적..

6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net [BFS] 일반적인 2차원 배열에서 3차원 배열로 응용된 문제. 앞 뒤 좌 우 뿐만 아니라 상 하 까지 탐색 범위를 늘려주고 BFS를 실행하되, 탈출구를 찾았는지 못찾았는지에 대한 분기가 필요하다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue;..

1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net [BFS + Bit Masking(비트마스킹)] 우선, 열쇠가 a, b, c, d, e, f 6개이므로 6자리 이진수의 최대값인 111111만큼의 visit 배열이 필요하다. 111111 = 63이다. 그러나 배열의 Index에 적용하기 위해선 +1을 해주어야 하므로 visit[64]개 만큼의 공간이 필요하다. 그럼 visit은 다음과 같이 정의될 수 있다. boolean[][][] visit = new boolean[64][51]..

비트 마스킹은 알고리즘이라기 보다는 비트의 연산을 이용한 테크닉이라고 볼 수 있다. &, |, ^등의 비트 연산을 활용하여 정수의 이진 비트를 처리하는 작업이다. 그렇게 많이 사용될 일은 없겠으나, 가끔 사용해야 할 때 비트 마스킹을 사용하면 훨씬 빠르고 간단하게 코드를 구현할 수 있다. 비트 마스킹의 장점은 다음과 같다. 메모리를 적게 사용할 수 있다 프로그램이 빠르게 동작 소스코드가 직관적이게 된다 가령 미로를 탈출하는 시뮬레이션에서 코드를 구현할 때, 필요한 열쇠가 6개(a, b, c, d, e, f)라고 하자. 현재 이 중에 어떤 열쇠를 갖고 있는지를 어떻게 저장할 것이며, 특정한 열쇠가 필요한 상황에서 그 열쇠가 있는지 어떻게 판단할 것인가. 방법은 아주 다양하다. List, Set 같은 Col..

4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net [2개의 BFS] [백준] 5427번 : 불 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나 dev-gorany.tistory.com 위 문제와 매우 유사한 문제. 이번에는 map[r+2][c+2]의 배열을 만들어, 주어진 맵 테두리를 건물 밖으로 생각하고 풀었다. 이렇게 하면 좌표의 범위에 신경써야하는..

1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net [우선순위 큐 + BFS] 우선순위 큐를 사용한 이유에 대해서는 이따 반례와 함께 언급하고, 큐에 들어가야 하는 원소는 4가지 이다. 위치의 좌표(y, x), direction, 명령을 실행한 횟수(cnt)이다. 방향은 4가지 (동:1, 서:2, 남:3, 북:4)이고, 각 칸으로 최대 3칸 까지 갈 수 있으므로, int[][] X = {{1, 2, 3}, {-1, -2, -3}, {0, 0, 0}, {0, 0, 0}} int[][] Y = {{0, 0, 0}, {0, 0,..

5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net [BFS] 이 문제를 depth가 2 이하인 곳만 탐색하는 DFS로 풀어보려 했으나 6 5 1 2 1 3 3 4 2 3 4 5 의 예제 입력에서, 3 -> 4를 도달하지 못한다. 1->2 그리고 2->3을 방문하기 때문에 1 -> 3, 3 -> 4를 가지 못하는 것이다. 이미 3 정점을 방문했기 때문이다. 그래서 한 층씩 탐색하는 BFS가 가장 적합한 방법이라고 생각된다. # Code public class Main { static class Element{ i..