CodeDrive

문제:

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력:

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

풀이방법:

 3중 배열을 사용하거나 2중 배열 2개를 사용하는 bfs 문제다. 대부분의 bfs 문제들은 방문 여부를 기록하는 2중 배열을 사용하는데, 이 문제에서는 도중에 한 개의 벽을 부수고 이동할 수 있다는 점 때문에 3중 배열을 사용하도록 한다. 3중 배열 중 앞 두 값은 일반적인 좌표 탐색을 위해 사용되고, 맨 마지막 값은 broken으로써 0과 1만을 가지는 값으로 사용한다. 즉, broken이 처음에는 0으로 진행하다가, 부술 수 있다면 broken이 1로 이동하여 시간 손실 없이 bfs를 계속해서 진행할 수 있도록 한다.

 visited에다가 한 step씩 진행하면서 거리를 기록하며, 최종적으로 목표하는 점의 broken의 0과 1을 모두 탐색하도록 한다. 만약 두 값 모두 있다면 둘 중 작은 값으로, 하나만 있다면 그 값을 출력하고 없다면 -1을 출력하면 된다.

문제링크:

https://www.acmicpc.net/problem/2206

문제:

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력:

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력:

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

풀이방법:

 다익스트라 알고리즘을 사용하는 기본적인 문제다. dp를 inf 값으로 초기화한 뒤 주어진 시작점으로부터 다익스트라 알고리즘을 사용해서 최단 경로 알고리즘을 구하면 된다. 다익스트라 알고리즘에 대한 설명은 다른 게시글에서 업로드 할 예정이다.

문제링크:

https://www.acmicpc.net/problem/1753

문제:

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력:

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력:

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

풀이방법:

**python3이 아닌 pypy3으로 통과한 문제입니다.**

플로이드-와샬 알고리즘을 적용하면 쉽게 풀 수 있는 문제다. 플로이드-와샬 알고리즘은 주어진 그래프의 경로로 가중치를 초기화한 후 i에서 j로 가는 경로에 k가 추가 되었을 때, 이전의 경로의 가중치보다 작아지는지 확인하면 된다. 

이 과정을 마친 후에 a to b가 inf가 아니면 -1을, b to a가 inf가 아니면 1을 inf면 0을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/1613

문제:

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬으 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.

지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력:

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

풀이방법:

visited 배열과 bfs를 이용해서 섬의 개수를 세도록 한다.

우선 visited 배열을 만들고, 이를 countLand라는 함수에게 넘겨준다. countLand에서는 주어진 지도를 반복문으로 반복하면서 방문하지 않은 땅이라면 bfs 함수로 들어갈 수 있도록 하며, 이 때마다 count를 하나씩 늘려주는 역할을 한다.

bfs는 일반적인 bfs 함수와 동일하고, 다른점이 있다면 이 문제에서는 대각선까지도 이동이 가능하기 때문에 더 많은 상황을 고려해 줘야 한다.

문제링크:

https://www.acmicpc.net/problem/4963