사전에는 순서라는 개념이 없고 index는 굳이 정수가 아니더라도 된다. 이러한 점 때문에 리스트, 사전 둘 다 사용 가치가 있다.
사전활용법
my_family={
'아빠': '김동식',
'엄마': '이윤경',
'아들': '김태헌',
'딸': '김주영'
}
#value 값들이 필요할 때
print(my_family.values())#dict_values(['김동식', '이윤경', '김태헌', '김주영'])
#값이 있는지 확인
print('김태헌' in my_family.values())#True
#이 값들로 반복문을 돌고 싶을 때
for value in my_family.values():
print(value)
#키 값을 받고 싶을 때
print(my_family.keys())#dict_keys(['아빠', '엄마', '아들', '딸'])
#key와 value 모두 같이 받아오려고 할 때
for key,value in my_family.items():
print(key,value)
print(True and True)#True
print(True and False)#False
print(False and True)#False
print(False and False)#False
print(True or True)#True
print(True or False)#True
print(False or True)#True
print(False or False)#False
알고스팟 운영진이 모두 미로에 갇혔다. 미로는 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)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.
예제 입력 1
3 3
011
111
110
예제 출력 1
3
예제 입력 2
4 2
0001
1000
예제 출력 2
0
예제 입력 3
6 6
001111
010000
001111
110001
011010
100010
예제 출력 3
2
[문제 해설]
이 문제는 벽에 대한 것을 어떻게 해결해야될까가 고민이였다. 벽을 부수는 횟수를 최소한으로 해서 탈출을 해야 한다. 사실 벽을 부순다는 행위를 거리의 길이 즉 가중치라고 생각하면 된다. 그래서 거리가 짧은 곳으로 다녀 목적지까지 도달하게 해주는 다익스트라 알고리즘을 사용하면 된다. 다익스트라 알고리즘보다는 거의 BFS를 사용해서 푼 것 같다.
BFS대로 푸는데 최대한 벽이 없는 곳으로 가는 것이 유리하다. 벽이 없는 곳을 만났을 때는 큐에서 appendleft를 이용하여 먼저 가게 하고 벽이 있는 곳을 만나면 그냥 append를 통해 큐에 추가해준다.
from collections import deque
m,n=map(int,input().split())
graph=[list(map(int,input())) for _ in range(n)]
bback=[[-1]*m for _ in range(n)]#가중치
dx=[-1,1,0,0]#상하좌우
dy=[0,0,-1,1]#상하좌우
q=deque()
q.append((0,0))
bback[0][0]=0
while q:
x,y = q.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or nx>=n or ny<0 or ny>=m:
continue
if bback[nx][ny]==-1:
if graph[nx][ny]==0:
bback[nx][ny]=bback[x][y]
q.appendleft((nx,ny))
elif graph[nx][ny]==1:
bback[nx][ny]=bback[x][y]+1
q.append((nx,ny))
print(bback[n-1][m-1])
DFS는 한 사람이 미로를 찾아 헤매는 과정과 비슷한 반면, BFS는 여러 명의 사람이 각기 서로 다른 갈림길로 흩어져서 길을 찾는 것과 비슷하다. 이때 각자 실뭉치를 가지고 풀어 놓았다가 되감으면서 새로운 길을 탐색한다. 길을 따라가다 갈림길이 나오면 사람들을 나눠 다시 각자 새로운 길을 탐색하고, 다시 갈림길을 만나 새로 탐색할 길이 하나로 모이면, 나뉘어 탐색하던 사람들이 다시 모여서 함께 탐색한다.
다익스트라 알고리즘은 이때 먼저 도착한 사람의 실뭉치를 사용한다.
다익스트라 알고리즘은 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다. 만일 이후에 더 짧은 경로가 존재한다면 다익스트라 알고리즘의 논리적 기반이 무너진다. 이때는 모두 값을 더해서 양수로 변환하는 방법이 있다. 같은 이유로 최장거리를 구하는 데에는 다익스트라 알고리즘을 사용할 수 없다.
다익스트라 알고리즘은 매번 가장 비용이 적은 노드를 선택해서 임의의 과정으로 반복하기 때문에 그리디 알고리즘으로 분류된다 알고리즘의 과정은 다음과 같다.
1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화 한다. (초기에는 전부 무한대 값으로 초기화 한다)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정의 3,4를 반복한다.
다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다. 3번에서 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해서 4번을 수행한다는 점에서 그리디 알고리즘으로 볼 수 있다.
다익스트라 최단 경로 알고리즘에서는 '방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택'하는 과정을 반복한다. 그래서 최적의 해답을 구할 수 있다.
다익스트라 알고리즘 구현
1. 첫번째 방법
import sys
input = sys.stdin.readline
INF = int(1e9)#무한
#노드의 개수, 간선의 개수 입력 받기
n,m = map(int,input().split())
#시작 노드
start = int(input())
#각 노드에 연결되어 있는 노드에 대한 정보 담는 리스트 만들기
graph=[[] for i in range(n+1)]
#방문 리스트
visited = [False]*(n+1)
#최단 거리 테이블 무한으로 초기화
distance = [INF]*(n+1)
#모든 간선 정보 입력받기
for _ in range(m):
a,b,c = map(int,input().split())
#a번 노드에서 b번 노드로 가는 비용이 c
graph[a].append((b,c))
#방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
min_value = INF
index =0 #가장 최단 거리가 짧은 노드
for i in range(1,n+1):
if distance[i]<min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
#시작 노드 초기화
distance[start]=0
visited[start]=True
for j in graph[start]:
distance[j[0]]=j[1]
#시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
for i in range(n-1):
#현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
now = get_smallest_node()
visited[now]=True
#현재 노드와 연결된 다른 노드를 확인
for j in graph[now]:
cost = distance[now]+j[1]
#현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost<distance[j[0]]:
distance[j[0]]=cost
#다익스트라 알고리즘 실행
dijkstra(start)
#모든 노드로 가기 위한 최단 거리를 출력
for i in range(1,n+1):
#도달할 수 없는 경우, 무한(INFINITY)출력
if distance[i]==INF:
print("INFINITY")
#도달할 수 있는 경우 거리를 출력
else:
print(distance[i])
-첫번째 다익스트라 알고리즘의 시간 복잡도 : O(N^2)
다익스트라 알고리즘의 코드를 보면 전체 노드에서 for문을 돌릴때 get_smallest_node()함수를 계속 사용한다.
get_smallest_node()함수에서는 전체 노드에서 제일 거리가 짧은 노드를 찾기 때문에 O(V)번 걸린다. 결국 시간복잡도는 O(V^2)이 된다. 따라서 노드의 개수가 10000개를 넘어가면 문제를 해결할 때 이 방법을 쓰면 시간 초과가 날 수 있다.
2. 두번째 방법
-두번째 다익스트라 알고리즘의 시간 복잡도 : O(MlogN)
이 방법은 최악의 경우에도 O(MlogN)을 보장하여 해결할 수 있다. 여기서 N은 노드의 개수, M은 간선의 개수에 해당한다. 첫번째 알고리즘에서 최단 거리 노드를 하나하나씩 탐색했다면 이 과정에서 시간을 단축하여 알고리즘을 개선하였다. 여기서는 힙 자료구조를 사용한다. 힙 자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다. 이 과정에서 로그 시간이 걸린다.
데이터의 개수가 N개일 때, 힙 자료구조에 N개의 데이터를 모두 넣은 뒤에 다시 모든 데이터를 꺼낸다고 해보자. 이때의 시간 복잡도는 어떻게 될가? 삽입할 때는 O(logN)의 연산을 N번 반복하므로 O(NlongN)이고 삭제할 때에서 O(logN)의 연산을 N번 반복하므로 O(NlogN)이다. 따라서 전체 연산 횟수는 대략 2NlogN으로 시간복잡도는 O(NlogN)이 될 것이다.
최소 힙을 이용하는 경우 힙에서 원소를 꺼내면 '가장 값이 작은 원소'가 추출되는 특징이 있으며, 파이썬의 우선순위 큐라이브러리는 최소 힙에 기반한다. 우선순위 큐를 이용해서 시작 노드로부터 '거리'가 짧은 노드 순서대로 큐에서 나올 수 잇도록 다익스트라 알고리즘을 작성하면 된다.
1번 방법에서 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다고 보면 된다. 파이썬의 heapq 라이브러리는 원소로 튜플을 입력받으면 튜플의 첫 번째 원소를 기준으로 우선순위 큐를 구성한다. 따라서 (거리, 노드 번호) 순서대로 튜플 데이터를 구성해 우선순위 큐에 넣으면 거리순으로 정렬된다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
#노드의 개수, 간선의 개수 입력받기
n,m = map(int,input().split())
#시작 노드 번호를 입력받기
start = int(input())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph=[[] for i in range(n+1)]
#최단 거리 테이블을 모두 무한으로 초기화
distance=[INF]*(n+1)
#모든 간선 정보를 입력받기
for _ in range(m):
a,b,c = map(int,input().split())
#a번 노드에서 b번 노드로 가는 비용이 c
graph[a].append((b,c))
def dijkstra(start):
q=[]
#시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
heapq.heappush(q,(0,start))
distance[start]=0
while q:#큐가 비어있지 않다면
#가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist,now = heapq.heappop(q)
#현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now]<dist:
continue
#현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
#현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost,i[0]))
#다익스트라 알고리즘 수행
dijkstra(start)
#모든 노드로 가기 위한 최단 거리 출력
for i in range(1,n+1):
if distance[i]==INF:
print("INFINITY")
else:
print(distance[i])
힙 자료구조는 완전 이진 트리의 일종으로 우선순위 큐(Prioirty Queue)를 위하여 만들어진 자료구조이다. 힙을 사용한 모듈은 heapq 모듈이다. 파이썬은 최소 힙만 구현되어 있다. 최소 힙은 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값을 갖게 되며, 우선순위 큐에서 가장 작은 값을 추출하는 것은 매번 힙의 루트를 가져오는 형태로 구현된다.
우선순위 큐(Prioirty Queue):
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다. 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 여러 개의 값들 중에서 최대값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 대표적으로 최댓값 추출을 보면 예를 들어 큐에 [1, 4, 5, 3, 2] 가 들어 있고 최댓값을 추출하는 우선순위 큐가 있다고 가정하자. 이 경우 항상 남아 잇는 요소들의 최댓값이 우선순위에 따라 추출되어 5, 4, 3, 2, 1 순으로 추출된다.
힙의 특징
힙에서 착각하기 쉬운 특징은, 힙은 정렬된 구조가 아니라는 점이다. 최소 힙의 경우 부모 노드가 항상 작다는 조건만 만족할 뿐, 서로 정렬되어 있지 않다. 예를 들어 오른쪽의 자식 노드가 더 커야될 것 같지만 왼쪽 노드보다 작은 경우도 얼마든지 있을 수 있다. 부모, 자식 간의 관계만 정의할 뿐, 좌우에 대한 관계는 정의하지 않기 때문이다.
자식이 둘인 힙은 특별히 이진 힙(Binary Heap)이라 하며, 대부분은 이진 힙이 널리 사용된다. 힙을 저장하는 표준적인 자료구조는 배열이다. 구현을 쉽게 하기 위해 첫 번째 인덱스인 0은 사용되지 않는다. 힙은 여러 알고리즘에서 사용되는데 우선 순위 큐 뿐만 아니라 다익스트라 알고리즘, 최소 신장 트리를 구현하는 프림 알고리즘 등에도 활용된다.
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
문제를 해석하면 1은 익은 토마토, 0은 익지 않은 토마토 -1은 토마토가 없는 곳이다. 하루가 지나면 1 옆에 0은 1로 변한다. (옆이라는 것은 대각선이 아닌 가로, 세로로 인접한 곳을 의미)
dx,dy를 통해 상하좌우를 탐색해야 되므로 bfs를 떠올렸다. 일단 bfs로 근처 0이 1로 변하는 것을 짜고 정답인 걸리는 시간은 나중에 생각해야 겠다고 결정했다.
입력을 받고, bfs에 사용되는 큐에는 토마토 중 익은것인 1이 되어있는 것을 넣어주었다.
from collections import deque
m,n = map(int,input().split())
tomato=[]
for i in range(n):
tomato.append(list(map(int,input().split())))
queue=deque()
for i in range(n):
for j in range(m):
if tomato[i][j]==1:
queue.append((i,j))
(bfs에서는 deque를 사용하므로 collections import해주었다.)
그리고 bfs를 사용해서 1. 범위를 넘어간 곳이면 continue 2. 0인 곳을 만나면 1로 바꾸어주고 큐에 넣어줌. 3. -1인 곳도 그냥 continue
from collections import deque
m,n = map(int,input().split())
tomato=[]
for i in range(n):
tomato.append(list(map(int,input().split())))
queue=deque()
for i in range(n):
for j in range(m):
if tomato[i][j]==1:
queue.append((i,j))
dx = [-1, 1, 0, 0] # 상, 하, 좌, 우
dy = [0, 0, -1, 1]
while queue:
x,y=queue.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or nx>=n or ny<0 or ny>=m:
continue
if tomato[nx][ny]==0:
tomato[nx][ny]=1
queue.append((nx, ny))
if tomato[nx][ny] == -1:
continue
그리고 이제 여기까지 되었으면 마지막 단계인 토마토가 다익는데 걸리는 기간을 확인해야 된다. 여기서 떠올린 생각은 토마토가 완성되는데 걸리는 시간은 큐에 원소의 갯수에 따라 달라질 수 있다는 것이다.
만약 처음에 tomato맵에서 1이었던 것이 2개이면 동시에 bfs함수를 돌려서 그날에 익는 갯수를 확인해야 될 것이다. 그러므로 for문을 통해 tomato맵에서 1이었던 것의 갯수만큼만 반복해주면 된다.
(이미 한것에 한해서는 bfs함수를 해서 주위엔 익은 상태이기 때문에 신경을 안써주어도 되기 때문)
[최종 정답]
from collections import deque
m, n = map(int, input().split())
tomato = []
for _ in range(n):
tomato.append(list(map(int, input().split())))
# 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않음
dx = [-1, 1, 0, 0] # 상, 하, 좌, 우
dy = [0, 0, -1, 1]
queue = deque()
for i in range(n):
for j in range(m):
if tomato[i][j]==1:
queue.append((i, j))
day = 1
count = len(queue)
while queue:
for i in range(count):
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or nx>=n or ny<0 or ny>=m:
continue
if tomato[nx][ny] == 0:
tomato[nx][ny] = 1
queue.append((nx, ny))
if tomato[nx][ny] == -1:
continue
day+=1
count=len(queue)
answer=0
for i in range(n):
for j in range(m):
if tomato[i][j]==0:
answer=-1
if answer!=-1:
answer=day
print(answer)
