20200323 알고리즘
1. 송아지 찾기
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요.
▣ 입력설명 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다.
▣ 출력설명 점프의 최소횟수를 구한다.
▣ 입력예제 1
5 14
▣ 출력예제 1
3
Solution
import sys
from collections import deque
sys.stdin = open("input65.txt", "rt")
if __name__ == '__main__':
n, m = map(int, input().split())
MAX = 10000
ch = [0] * (MAX + 1)
dis = [0] * (MAX + 1)
dis[n] = 0
dQ = deque()
dQ.append(n)
while dQ:
now = dQ.popleft()
if now == m:
break
for next in (now-1, now+1, now+5):
if 0 < next <= MAX:
if ch[next] == 0:
dQ.append(next)
ch[next] = 1
dis[next] = dis[now] + 1
print(dis[m])2. 사과나무 (BFS 활용)
현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저 있다. N의 크기는 항상 홀수이다. 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사 과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다.
만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다.
현수과 수확하는 사과의 총 개수를 출력하세요.
▣ 입력설명 첫 줄에 자연수 N(홀수)이 주어진다.(3<=N<=20) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 이 자연수는 각 격자안에 있는 사과나무에 열린 사과의 개수이다. 각 격자안의 사과의 개수는 100을 넘지 않는다.
▣ 출력설명 수확한 사과의 총 개수를 출력합니다.
▣ 입력예제 1
5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19▣ 출력예제 1
379
Solution
import sys
from collections import deque
sys.stdin = open("input66.txt", "rt")
if __name__ == '__main__':
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ch = [[0] * n for _ in range(n)]
dQ = deque()
dQ.append((n // 2, n // 2))
tot = a[n // 2][n // 2]
ch[n//2][n//2] = 1
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
L = 0
while True:
if L == n // 2:
break
size = len(dQ)
for i in range(size):
tmp = dQ.popleft()
for j in range(4):
x = tmp[0] + dx[j]
y = tmp[1] + dy[j]
if ch[y][x] == 0:
tot += a[y][x]
ch[y][x] = 1
dQ.append((x, y))
L += 1
print(tot)3. 미로의 최단거리 통로
자연수 N이 주어지면 7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자 의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면
위와 같은 경로가 최단 경로이며 경로수는 12이다.
▣ 입력설명 첫 번째 줄에 자연수 N(1<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.
▣ 출력설명 첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.
▣ 입력예제 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 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0▣ 출력예제 1
12
Solution
import sys
from collections import deque
sys.stdin = open("input67.txt", "rt")
if __name__ == '__main__':
a = [list(map(int, input().split())) for _ in range(7)]
dis = [[0] * 7 for _ in range(7)]
dQ = deque()
dQ.append((0, 0))
a[0][0] = 1
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
while dQ:
size = len(dQ)
tmp = dQ.popleft()
for i in range(4):
x = tmp[0] + dx[i]
y = tmp[1] + dy[i]
if 0 <= x < 7 and 0 <= y < 7 and a[y][x] == 0:
a[y][x] = 1
dis[y][x] = dis[tmp[1]][tmp[0]] + 1
dQ.append((x, y))
if dis[6][6] == 0:
print(-1)
else:
print(dis[6][6])
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)