먹여살릴냥꽁이가있습니다.

Floyd Warshall 

• 모든 정점에서 모든 정점으로의 최단 경로를 찾는 알고리즘
• Dijkstra 알고리즘과 다르게 한 장점으로부터 모든 정점으로의 최단경로가 아닌 모든 정점 사이의 최단경로를 구한다는 점과 음수 가중치가 있어도 최단 경로를 구할 수 있다점에서 다익스트라 알고리즘과 차이점이있다.

최단경로 찾는 과정

• 출발지에서 목적지로 가는 경우와 출발지에서 경유지를 통해 목적지를 가는 경우를 비교해 둘 중 더 빠른 경우가 존재한다면 더 빠른 경우로 최단 거리를 계산한다.

구현

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w, h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제

코드

풀이 방법

빌딩의 지도가 주어졌을 때, 상근이가 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 문제였습니다.

저는 상근이 위치정보를 person큐와 불의 위치정보를 fire큐에 넣어주었습니다.

불과 상근이는 동시에 움직이므로 bfs를 이용해 불을 먼저 움직인 뒤, 상근이를 움직였습니다. 만약 상근이가 다음 움직일 위치가 배열의 범위를 넘어선다면 출구로 빠져나간 것이므로 리턴을 통해 걸린 시간을 반환해주었습니다.

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

예제

코드

풀이 방법

미로의 가장 왼쪽 위인(0,0)에서 가장 오른쪽 아래(M-1, N-1)의 위치로 이동하기 위해 최소한으로 몇 개의 벽을 부수는지 알아내는 문제였습니다. 저는 bfs()를 사용해서 구현했습니다. 먼저 시작점인 (0,0)과 함께 벽을 부슨 개수를 기억하기 위해 벽을 부순 횟수인 cnt와 함께 우선순위 큐에 저장해주었습니다. 우선순위 큐를 사용한 이유는 가장 적은 수의 벽을 부순 개수를 찾아야 하기 때문에 우선순위 큐를 이용하여 cnt값이 가장 작은 것을 기준으로 진행하였습니다. 만약 도착점인 (M-1, N-1)에 도착했다면 도착지까지의 벽을 부순 횟수인 cnt 값을 리턴해 주었습니다.

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

예제

코드

풀이 방법

치즈가 모두 녹아서 없어지는 데 걸리는 시간과, 치즈가 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여 있는 칸의 개수를 구하는 문제였습니다.

저는 DFS를 이용해 문제를 풀었습니다. 여기서 주의할 점은 치즈의 구멍을 둘러싼 치즈는 녹지 않는다는 점입니다!

공기 중에 치즈를 놓으면 1초 뒤 그 치즈는 사라지게 됩니다. 저는 공기를 기준으로 상, 하, 좌, 우에 치즈가 있다면 그 치즈 자리를 2로 변경해주었습니다. 여기서 치즈 자리를 0이 아닌 2로 변경해주는 이유는 만약 바로 0으로 바꿔줬더라면 그 치즈 자리가 0이 되어 그 자리에서 상, 하, 좌, 우 에 있는 치즈 또한 공기 중에 놓여있어 사라지기 때문입니다. 그래서 dfs() 메서드를 통해 공기와 접촉한 치즈들의 자리를 2로 변경해준 뒤, check() 함수를 통해 위치의 값이 2인 곳을 0으로 바꿔주고 map에 치즈가 남아있는지 확인해주었습니다. 만약 치즈가 남아있지 않다면 반복문을 종료해 치즈가 모두 녹아서 없어지는 데 걸리는 시간과, 모두 녹기 한 시간 전에 남아있는 치즈 조각의 수를 출력해주었습니다.

문제

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

입력

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

예제

코드

풀이방법

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X, Y)에 존재하는 바이러스의 종류를 출력하는 문제였습니다.  번호가 낮은 종류의 바이러스부터 먼저 증식하기 때문에 바이러스 정보를 넣은 list를 먼저 정렬해주고 bfs를 이용해 상 하 좌 우로 확인하여 바이러스를 증식해나갔습니다. S초가 지난 후에는 반복문을 종료해 해당 (x, y)에 존재하는 바이러스의 종류를 출력해주었습니다.

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다.

테스트 케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

예제

코드

풀이방법

중요도가 높은 순서대로 출력하는데 큐에서 M번째 놓여 있는 정수가 몇 번째로 인쇄되는지 알아내는 문제였습니다.

저는 인덱스와 중요도를 저장하는 큐와 중요도 높은 순으로 정렬한 우선순위 큐를 이용하여 구현하였습니다.

먼저, 인덱스와 중요도를 큐와 우선순위 큐에 각각 저장한 뒤, 중요도 높은 문서부터 출력하기 위해 while문을 통해 우선순위 맨 앞에 저장된 중요도와 큐에 저장된 중요도를 비교해서 같으면 문제에서 원하던 정수이므로 그동안 출력한 횟수+1을 하여 출력해주고 같지 않을 경우 값을 맨 뒤에 저장해 우선순위 큐 맨 앞에 저장된 중요도와 같은 중요도를 찾을 수  있도록 구현했습니다.

문제

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"라고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165)라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.

이름(몸무게, 키) 덩치 등수

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C 뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

입력

첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다.

출력

여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백 문자로 분리되어야 한다.

예제

코드

풀이방법

학생 N명의 몸무게와 키가 담긴 입력을 통해 각 사람의 덩치 등수를 계산하는 문제였습니다.

저는 학생들의 키와 몸무게를 비교하기 위해서 list에 키, 몸무게, 나보다 덩치 큰 학생의 수를 저장할 수 있도록 하였습니다. 학생들의 정보를 다 저장하고 난 뒤, 첫 번째 학생부터 list에 들어있는 학생들과 비교해 자신보다 덩치가 큰 학생이 있는지 확인하여 자신보다 큰 학생들의 수를 cnt에 저장해주었습니다. 그리고 자신의 등수를 계산하는 문제이기 때문에 cnt에 +1을 더해줘 등수를 출력해주었습니다.

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

예제

코드

풀이방법

두 원소가 같은 집합에 포함되어 있는지를 확인하는 문제였습니다.

변수 o 가 0일 경우에는 두 집합을 합친다는 의미이므로 union()메소드를 통해 각 각의 루트를 찾아 두 원소가 다른 집합일 경우에는 집합의 루트를 같게 해 "두 원소가 같은 집합에 포함되어있다" 라고 표현해주었습니다.

변수 o가 1일 경우에는 두 원소가 같은 집합에 포함되어 있는지 확인하기 위해 find()메소드를 통해 루트가 같은지 확인하여 만약 같다면 yes를, 다르다면 no를 출력해주었습니다.

문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200 이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000 이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

출력

첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

예제

코드

풀이방법

도시의 연결 정보를 통해 여행 계획을 바탕으로 첫 번째 여행 할 도시를 기준으로 다음 여행할 도시가 첫번 째 도시와 같은지 확인하여 만약 다를 경우 여행 계획에 속한 도시들을 순서대로 여행할 수 없으니 no를 출력하고 여행 계획에 속한 도시들을 순서대로 여행할 수 있으면 yes를 출력해주었습니다.