알고리즘90 Algorithm - 안전영역(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [안전영역(DFS)] 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음 해당 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어지는지를 조사하려고 한다. 이 때, 문제를 단순화하기 위해 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며, 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 이제 N=5인 지역에 많은 비가 .. 2022. 1. 14. Algorithm - 섬나라 아일랜드(BFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [섬나라 아일랜드(BFS)] 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 자연수 N(3 ≤ N ≤ 20)이 주어진다. 두 번째 줄부터 격자판 정보가 주어진다. *출력 설명 첫 번째 줄에 섬의 개수를 출력한다. 풀이(Python) 답안 import sys from collections import deque sys.stdin = open('AA/input_68.txt', 'rt') dx.. 2022. 1. 13. Algorithm - 단지 번호 붙이기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [단지 번호 붙이기(DFS)] 그림 1과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 참고로, 대각선상에 집이 있는 경우는 연결된 것이 아니다. 그림2는 그림1을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에는 지.. 2022. 1. 12. Algorithm - 등산 경로(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [등산 경로(DFS)] 등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있다. 마을 뒷산의 형태를 나타낸 지도는 N*N 구역으로 나뉘어져 있으며, 각 구역에는 높이가 함께 나타나 있다. N=5이면, 마을 뒷산의 형태를 나타낸 지도는 아래와 같이 표현된다. 어떤 구역에서 다른 구역으로 등산을 할 때에는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있다. 등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳이다. (단, 출발지와 목적지는 유일함) 지도가 주어지면 출발지에서 도착지로 갈 수 .. 2022. 1. 11. Algorithm - 미로 탐색(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [미로 탐색(DFS)] 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하시오. 격자판의 움직임은 상하좌우로만 움직이며 미로가 아래와 같다면 위의 지도의 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다. 참고로, 격자판의 1은 벽이고 0은 통로이다. *입력 설명 7*7 격자판의 정보가 주어진다. *출력 설명 첫 번째 줄에 경로의 가지수를 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_65.txt', 'rt') dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] .. 2022. 1. 11. Algorithm - 미로의 최단거리 통로(BFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [미로의 최단거리 통로(BFS)] 7*7 격자판 미로를 탈출하는 최단경로의 수를 출력하는 프로그램을 작성하시오. 단, 경로의 수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미하며 출발점은 격자의 (1, 1) 좌표이고 탈출 도착점은 (7, 7) 좌표이다. 또한, 격자판의 1은 벽이고 0은 도로이다. 참고로, 격자판의 움직임은 상하좌우로만 움직이며 미로가 아래와 같다면 다음의 경로가 최단경로(12)이다. *입력 설명 7*7 격자판의 정보가 주어진다. *출력 설명 첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 단, 도착할 수 없는 경우에는 -1을 출력한다. 풀.. 2022. 1. 9. 이전 1 2 3 4 5 6 7 ··· 15 다음
