알고리즘 | 음료수 얼리기 문제 (BFS와 DFS로 각각 풀어보기)
더보기 N by M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0 칸막이가 존재하는 부분은 1입니다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 판단합니다. 이러한 경우에서 얼음 틀의 모양이 그래프로 주어진다면 생성되는 아이스크림의 갯수는 몇 개일까요? graph_45 = [ [0,0,1,1,0], [0,0,0,1,1], [1,1,1,1,1], [0,0,0,0,0] ] n = 4 m = 5 첫째 / BFS 방식으로 풀기 출발점에서부터 점진적으로 진행해가는 방식으로 접근하는 경우 BFS를 고려해볼 수 있습니다. 일단 BFS니까 아묻따 디큐부터 임포트해주고 시작합니다. from collections import deque 1. 함수를 작성합니다. 입력받..
2024. 4. 2.
알고리즘 | BFS 활용하여 미로 찾기 문제 풀기
백준 2178번 미로탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net n = 4 m = 6 graph = [ [1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1] ] 0과 1로 이루어진 n * m 크기의 미로 그래프가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동..
2024. 4. 1.
알고리즘 | BFS 활용하여 특정 도시 거리 계산 문제 풀기
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 ..
2024. 4. 1.
알고리즘 | queue(FIFO) 속도이슈를 해결할 수 있는 deque
from collections import deque 디큐는 속도가 빠른 리스트로 생각해도 좋다. 코딩 테스트에서 파이썬으로 Queue, BFS, FIFO 방식의 알고리즘 접근이 필요할 때 리스트를 디큐로 바꾸어주면 속도 이슈 해결이 가능하다. a_list = [1, 2, 3, 4, 5] # [1, 2, 3, 4, 5] a_dq = deque(a_list) # deque([1, 2, 3, 4, 5]) 이렇게 간단하게 디큐 함수로 바꾸어주기만 하면 된다. a_dq.pop() a_dq.popright() # 5 a_dq.popleft() # 1 a_dq # deque([2, 3, 4]) a_dq.append(1004) # deque([2, 3, 4, 1004]) 디큐 맨 마지막 값을 뺄 때 : .pop() ..
2024. 4. 1.
알고리즘 | 탐색 기본, DFS / BFS
엣지를 따라 모든 노드를 방문하는 것을 그래프 탐색이라고 한다. 대표적으로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있다. Depth First Search (깊이 우선 탐색) 깊이 우선 탐색은 기본적으로 Stack이다. (Last In First Out) 오른쪽 왼쪽 상관은 없음 예제 graph_list = [ [], # 0번 도시(없음) [2, 3, 8], # 1번 도시 [1, 7], # 2번 도시 [1, 4, 5], # 3번 도시 [3, 5], # 4번 도시 [3, 4], # 5번 도시 [7], # 6번 도시 [2, 6, 8], # 7번 도시 [1, 7] # 8번 도시 ] 1번 도시 방문 To do : [2, 3, 8] 2번 도시 방문 To do : [1, 7] -> 1번은 됐고 7번 ..
2024. 4. 1.
