20200325 알고리즘
1. 미로탐색
자연수 N이 주어지면 7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자 의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면
위와 같은 경로가 최단 경로이며 경로수는 12이다.
▣ 입력설명 첫 번째 줄에 자연수 N(1<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.
▣ 출력설명 첫 번째 줄에 경로의 가지수를 출력한다.
▣ 입력예제 1
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0▣ 출력예제 1
8
Solution
import sys
sys.stdin = open("input68.txt", "rt")
def DFS(x, y):
global cnt
if x == y == 6:
cnt += 1
else:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < 7 and 0 <= ny < 7 and board[ny][nx] == 0:
board[ny][nx] = 1
DFS(nx, ny)
board[ny][nx] = 0
if __name__ == '__main__':
board = [list(map(int, input().split())) for _ in range(7)]
cnt = 0
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
board[0][0] = 1
DFS(0, 0)
print(cnt)2. 등산경로
등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있습니다. 마을 뒷산의 형태를 나타낸 지도는 N*N 구역으로 나뉘어져 있으며, 각 구역에는 높이가 함께 나타나 있습니다. N=5이면 아래와 같이 표현됩니다.
어떤 구역에서 다른 구역으로 등산을 할 때는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있도록 등산로를 설계하려고 합니다. 등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳입니다. 출발지와 목적지는 유일합니다. 지도가주어지면출발지에서도착지로갈수있는 등산경로가몇가지인지구하는프로그 램을 작성하세요.
▣ 입력설명 첫 번째 줄에 N(5<=N<=13)주어지고, N*N의 지도정보가 N줄에 걸쳐 주어진다.
▣ 출력설명 등산경로의 가지수를 출력한다.
▣ 입력예제 1
5
2 23 92 78 93
59 50 48 90 80
30 53 70 75 96
94 91 82 89 93
97 98 95 96 100▣ 출력예제 1
5
Solution
import sys
sys.stdin = open("input69.txt", "rt")
def DFS(L):
global cnt
if L == e:
cnt += 1
else:
x, y = L
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if 0 <= xx < n and 0 <= yy < n and board[y][x] < board[yy][xx]:
DFS((xx, yy))
if __name__ == '__main__':
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
s = (0, 0)
e = (0, 0)
for y, a in enumerate(board):
for x, b in enumerate(a):
if b < board[s[1]][s[0]]:
s = (x, y)
if b > board[e[1]][e[0]]:
e = (x, y)
cnt = 0
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
DFS(s)
print(cnt)3. 단지 번호 붙이기
그림1과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸 다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.
대각선상에 집이 있는 경우는 연결된 것이 아니다. 그림2는 그림1을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지 에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
▣ 입력설명 첫 번째줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력 되고 그 다음 N줄에는 각각 N개의 자료(0 혹은 1)가 입력된다
▣ 출력설명 첫 번째줄에는 총 단지수를 출력하시오. 그리고 각 단지내의 집의 수를 오름차순으로 정렬하 여 한줄에 하나씩 출력하시오
▣ 입력예제 1
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000▣ 출력예제 1
3
7
8
9Solution ( DFS )
import sys
sys.stdin = open("input70.txt", "rt")
def DFS(x, y):
global cnt
board[y][x] = 0
cnt += 1
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if 0 <= xx < n and 0 <= yy < n and board[yy][xx] == 1:
DFS(xx, yy)
if __name__ == '__main__':
n = int(input())
board = [list(map(int, input())) for _ in range(n)]
res = list()
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
for y in range(n):
for x in range(n):
if board[y][x] == 1:
cnt = 0
DFS(x, y)
res.append(cnt)
print(len(res))
for v in sorted(res):
print(v)Solution (BFS)
import sys
from collections import deque
sys.stdin = open("input70.txt", "rt")
def BFS(a, b):
dQ = deque()
dQ.append((a, b))
board[b][a] = 0
cnt = 1
while dQ:
x, y = dQ.popleft()
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if 0 <= xx < n and 0 <= yy < n and board[yy][xx] == 1:
dQ.append((xx, yy))
cnt += 1
board[yy][xx] = 0
return cnt
if __name__ == '__main__':
n = int(input())
board = [list(map(int, input())) for _ in range(n)]
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
res = list()
for y in range(n):
for x in range(n):
if board[y][x] == 1:
res.append(BFS(x, y))
print(len(res))
for v in sorted(res):
print(v)
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)