오늘 팀원들과 아침에 그래프에 대해 발표했다.
상우형은 개괄적인 이론과 종류, 용어들을 설명했고,
의훈님은 성능과 관련하여 접근했다.
나는 그래프를 이해하기 위해 트리에 대해 설명했는데
서로 그래프에 대해 분석하고 잘못된 설명이 있으면 바로 잡으면서 개념을 조금 더 단단히 잡을 수 있게 됬다.
이런식으로 매일 발표를 진행할 텐데 앞으로도 좀 더 적극적으로 발표 내용을 만들어 가야겠다고 생각했다.
오늘은 BFS를 공부하겠다.
BaekJun - #2178 : 미로 탐색 (BFS)
미로의 최단 거리가 몇인지 확인하는 문제였다.
DFS로 많은 사람들이 푼 것 같은데
BFS가 가장 좋은 방법이라고 난 생각한다. 실제로 정글 커리큘럼 내 BFS 문제로 분류 되었기도 한다.
미로의 시작으로부터 방문을 시작하여 동서남북으로 다음을 고려하며 미로를 방문한다.
1. index의 끝인가?
2. '0'으로 설정된 벽인가?
3. 방문을 했는가?
난 방문시 이 세가지를 고려하여 if문을 사용했다.
다음은 처음 내가 시도한 코드이다.
from collections import deque
import copy
import sys
import heapq
n , m = map(int, sys.stdin.readline().strip().split())
maze = []
visited = [[False for _ in range(m)] for _ in range(n)]
for i in range(n):
maze.append(list(map(int,sys.stdin.readline().strip())))
def bfs(i,j):
global n
global m
queue = deque()
queue.append([i,j,1])
while queue:
now = queue.popleft()
visited[now[0]][now[1]] = True
if now[0] == n-1 and now[1] == m-1: #목적지에 도착했을 때 함수 종료
return now[2]
if not now[1] == m-1 :
if not visited[now[0]][now[1]+1] and maze[now[0]][now[1]+1] == 1:
queue.append([now[0],now[1]+1,now[2]+1])
if not now[0] == n-1 :
if not visited[now[0]+1][now[1]] and maze[now[0]+1][now[1]] == 1:
queue.append([now[0]+1,now[1],now[2]+1])
if not now[1] == 0 :
if not visited[now[0]][now[1]-1] and maze[now[0]][now[1]-1] == 1:
queue.append([now[0],now[1]-1,now[2]+1])
if not now[0] == 0 :
if not visited[now[0]-1][now[1]] and maze[now[0]-1][now[1]] == 1:
queue.append([now[0]-1,now[1],now[2]+1])
print(bfs(0,0))queue 안에 저장한 [? , ? , ?] 이 형식의 값은 pop 시에 now라는 곳에 리스트로 저장된다.
now[0]은 미로의 세로줄 , now[1]은 미로의 가로줄의 인덱스이고
now[2]는 지금까지 방문하면서 잰 거리의 값이다.
처음엔 이렇게 생각했다.
불필요한 길로 갔다가 막다른 길에 도달하여 다시 돌아오면 방문하면서 잰 거리들의 기록을 queue에 마구 넣어 뒤죽박죽이 되지 않을까?
하지만 그렇지 않다. 왜냐 ? 방문했던 곳은 돌아오지 않도록 설정했기에, 막다른길임을 인지하고 돌아오는 경우는 없다. 즉 막다른길에 도달한 queue의 경우는 새로운 동선을 append하지 않고 삭제되는 것이다.
그리고 막다른 길은 아니지만 낭비되어 빙 돌아온 동선은 어떻게 될까?
이 경우에는 이미 다른 경우에서 빙 돌아와 만나는 N차선의 회귀점은 최선의 동선의 queue가 방문한 이후기 때문에 visited로 막혀있어 데이터화 되어 queue에 기록되지 못한다.
따라서 결국 최선의 queue만이 결과를 도출하여 도착점인지 확인하는 if문에 도달하는 것이다.
그런데 문제는 위의 코드는 시간 초과가 발생된 코드이다.
너무 많은 탐색과 조건문에 시간이 많이 소요된 것이다.
첫번째 해결책으로 나는 visited 리스트를 없애고 maze의 지나온 길을 벽으로 만들기로 했다.
from collections import deque
import sys
n , m = map(int, sys.stdin.readline().strip().split())
maze = []
for i in range(n):
maze.append(list(map(int,sys.stdin.readline().strip())))
def bfs(i,j):
global n
global m
queue = deque()
queue.append([i,j,1])
while queue:
now = queue.popleft()
maze[now[0]][now[1]] = 0
if now[0] == n-1 and now[1] == m-1: #목적지에 도착했을 때 함수 종료
return now[2]
if not now[1] == m-1 :
if maze[now[0]][now[1]+1] == 1:
queue.append([now[0],now[1]+1,now[2]+1])
if not now[0] == n-1 :
if maze[now[0]+1][now[1]] == 1:
queue.append([now[0]+1,now[1],now[2]+1])
if not now[1] == 0 :
if maze[now[0]][now[1]-1] == 1:
queue.append([now[0],now[1]-1,now[2]+1])
if not now[0] == 0 :
if maze[now[0]-1][now[1]] == 1:
queue.append([now[0]-1,now[1],now[2]+1])
print(bfs(0,0))아이디어는 좋아 코드와 데이터 사용량은 줄었겠지만, 시간 초과의 문제는 해결되지 않았다.
두번째 방법으로 사용한건 'maze[now[0]][now[1]] = 0'의 순서 변경이다.
maze[now[0]][now[1]] = 0 이 코드는 방문한 길을 벽으로 만들어 다른 경로의 길이 들어오지 못하도록 visited의 역할을 하는 코드인데,
막다른 길을 간 경로의 경우 이 코드를 읽을 필요가 없기에 막다른 길이 아닌 것을 체크한 if 문 안으로 이동시켰더니 코드가 성공했다.
from collections import deque
import sys
n , m = map(int, sys.stdin.readline().strip().split())
maze = []
for i in range(n):
maze.append(list(map(int,sys.stdin.readline().strip())))
def bfs(i,j):
global n
global m
queue = deque()
queue.append([i,j,1])
while queue:
now = queue.popleft()
if now[0] == n-1 and now[1] == m-1: #목적지에 도착했을 때 함수 종료
return now[2]
if not now[1] == m-1 :
if maze[now[0]][now[1]+1] == 1:
queue.append([now[0],now[1]+1,now[2]+1])
maze[now[0]][now[1]+1] = 0
if not now[0] == n-1 :
if maze[now[0]+1][now[1]] == 1:
queue.append([now[0]+1,now[1],now[2]+1])
maze[now[0]+1][now[1]] = 0
if not now[1] == 0 :
if maze[now[0]][now[1]-1] == 1:
queue.append([now[0],now[1]-1,now[2]+1])
maze[now[0]][now[1]-1] = 0
if not now[0] == 0 :
if maze[now[0]-1][now[1]] == 1:
queue.append([now[0]-1,now[1],now[2]+1])
maze[now[0]-1][now[1]] = 0
print(bfs(0,0))
Dijkstra (다익스트라) 알고리즘
다익스트라 알고리즘은 가중치 그래프에서 쓰이는 알고리즘이다.
예를 들면 'A->F 로 가는 경로 중 가장 비용이 적게 드는 경로는?' 과 같은 문제에 쓰이는 알고리즘이다.
이 알고리즘은 우선순위 큐를 이용한 경우가 많은데 그 이유는
가장 가중치의 우선순위가 높은 정점부터 방문해 나가며 비교를 하기 때문이다.
가장 비용이 적게 드는 경로를 찾기 위해선 정점에서 비용이 낮은 경로부터 비교하는 것이 좋을 것이다.
이 알고리즘은 BFS를 발전시킨 케이스인데
그 이유는 BFS처럼 queue에 task를 넣어 너비 방문을 하는 것과 비슷하게
우선순위 큐에 정점을 넣고 빼며 방문을 하기 때문이다.
문제로 한번 설명해 놓겠다
BaekJun - #2665 : 미로 찾기 (다익스트라 가중치 이용)
검은 방 문을 최소로 열어서 끝방으로 도달해야 하는 문제이다.
다익스트라를 몰랐을 때는 어떻게 풀어야 할지 정말 어렵겠지만 다익스트라를 활용한다면 어렵지 않다.
가중치가 낮은 값을 가진 방문부터 연다는 메커니즘을 이용하여 방문을 연 횟수를 미로를 움직이면서 기억하는 방식으로 풀어냈다.
from collections import deque
import sys
import heapq
n = int(sys.stdin.readline())
rooms = []
for _ in range(n):
rooms.append(list(map(int,sys.stdin.readline().strip())))
for i in range(n):
for j in range(n):
if rooms[i][j] == 0:
rooms[i][j] = 1
elif rooms[i][j] == 1:
rooms[i][j] = 0
def room_for_dijkstra(startX,startY):
global n
heap = []
heapq.heapify(heap)
heapq.heappush(heap,[rooms[startX][startY],startX,startY])
while heap:
this = heapq.heappop(heap) #[룸의[x][y] 값 (비용) , x인덱스, y인덱스]
for i,j in (0,1),(1,0),(0,-1),(-1,0):
if this[1]+i>=n or this[1]+i<0 or this[2]+j>=n or this[2]+j<0:
continue
if rooms[this[1]+i][this[2]+j] < 0:
continue
if this[1]+i == n-1 and this[2]+j == n-1 :
return rooms[n-1][n-1]+this[0]
rooms[this[1]+i][this[2]+j] += this[0]
heapq.heappush(heap,[rooms[this[1]+i][this[2]+j],this[1]+i,this[2]+j])
rooms[this[1]][this[2]] = -10
answer = room_for_dijkstra(0,0)
print(answer)this는 현재의 방을 나타내고 현재의 방의 동서남북 위치를 파악하기 위해
for i,j in (0,1),(1,0),(0,-1),(-1,0):
를 사용했다.
가중치가 낮은 방문을 계속 열 것이기 때문에 먼저 0의 값을 가지는 방문을 모두 열고 나서
닫혀있는 1의 값의 공간을 탐색하기 시작한다.
만약 여러번 열어야 하는 길이 있다면 횟수가 기록되어
우선순위에서 밀려나게 될 것이기 때문에 최소의 값으로 도달한 횟수를 파악할 수 있다.
그리고 힙 안에 최소로 열었던 값을 기억하며 탐색을 계속 해 나가고 마지막으로 끝방에 도달하면 return을 할 수 있게 했다.
최소 신장 트리(MST : Minimum Spanning Tree)
최소 신장 트리란 모든 정점을 연결하면서도 그 연결된 가중치의 합이 최소가 되는 트리를 말한다.
대표적인 알고리즘으로 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있다.
이 알고리즘들은 그래프의 간선들을 가중치의 오름차순이나 내림차순으로 정렬한 후,
그리디 알고리즘을 사용해 스패닝 트리를 찾는다.
Kruskal 알고리즘
최적해를 찾는 그리디 알고리즘인 Kruskal 알고리즘은 최소 신장 트리를 찾는데 가장 보편적인 방법이다.
방법은 다음과 같다.
1. 간선을 가중치의 오름차순으로 정렬한다.
2. 간선이 작은 것 부터 하나씩 정점을 연결한다.
3. 싸이클을 만드는 간선이라면 버린다.
4. 정점 전부가 연결됬다면 최소 신장 트리 완성
코드에서 유심히 봐야할 부분은 바로 싸이클을 파악하는 알고리즘이다.
정점들을 연결하면 더 높은 수를 부모로 임의로 선정한 후 부모의 인덱스값에 자식을 저장한다.
이렇게 하여 주 실행 알고리즘에서는 부모를 찾아보고 같은지 아닌지 확인하여 두개의 정점이 싸이클을 이루는지 파악할 수 있다.
Prim 알고리즘
프림 알고리즘도 그리디 알고리즘이다.
방법은 다음과 같다.
1. 임의의 한 점을 선택하여 T 집합에 넣고 그 점과 연결된 모든 간선 중 최소의 가중치와 연결한다.
2. 1을 반복한다.
개념은 매우 간단하다.
Baekjun 문제를 풀며 해결해 나간 문법들
1. 재귀 에러의 해결 방안
재귀함수를 구현해 내는 것마저 머리아파 죽겠는데,,
마침내 만들어서 올바른 코드를 짜봤자 재귀에러가 뜨면 말짱 도루묵이다.
이 런타임 에러(RecursionError)를 해결하는 방법을 찾아보다가 기가막힌 방법이 있었다.
저 재귀 에러는 컴퓨터 내의 재귀 제한이 설정 되어 있는데 그 제한을 넘어가기 때문에 강제 종료를 시켜 발생한다.
따라서 간단하게 채점하는 컴퓨터의 재귀 제한을 넉넉하게 재 설정하는 방법을 사용했다.
방법은 간단하다.
최상단 import 선언 부 바로 밑에
sys.setrecursionlimit(10**8)
이 코드로 재귀제한을 넉넉하게 두게 했다.
10^8만큼으로 넓힌 이유는 보통의 백준 N 데이터의 제한이 10**8이라 그렇게 설정해 보았다.
결과는 성공!
2. 딕셔너리의 key 혹은 value 다루기
알고리즘을 풀다보면 딕셔너리의 value안에 list를 선언하는 경우가 많다.
이때 key의 value 리스트를 정렬하는 등의 조작을 하려면
`for key,value in dict.items()`
이 방식을 사용하여 key 와 value를 조작한 뒤 다시 dict에 삽입하면 된다.
'Jungle' 카테고리의 다른 글
| [TIL][Krafton Jungle] 2주차 - (4) : 위상정렬 알고리즘 (4) | 2023.10.22 |
|---|---|
| [TIL][Krafton Jungle] 2주차 - (3) : DFS 알고리즘 공부 (5) | 2023.10.21 |
| [TIL][Krafton Jungle] 2주차 - (1) : 트리 & 그래프 알고리즘 (1) | 2023.10.19 |
| [TIL][Krafton Jungle] 1주차 (sub) : 스택 문제 (0) | 2023.10.19 |
| [TIL][Krafton Jungle] 1주차 - (5) : 알고리즘 공부 마지막 (2) | 2023.10.18 |