본문 바로가기
반응형

BFS25

[BOJ][Python]14502 풀이 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net from collections import deque import copy import sys ssr = sys.stdin.readline def bfs(n, m, board, twos): dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)] q = deque(twos) while q: v_r, v_c = q.popleft() for dr, dc in dpos: pos_r, pos_c =.. 2023. 10. 21.
[BOJ][Python]12851 풀이 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net from collections import deque n, k = map(int, input().split()) visited = [0 for _ in range(200001)] visited[n] = 1 q = deque([(n, 0)]) ans = 100001 methods = [] while q: cur_pos, cur_time = q.popleft() .. 2023. 10. 14.
[BOJ][Python]2638 풀이 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def outer_air(): nomis = [] while q: r, c = q.popleft() for dr, dc in dpos: if 0 1: nomis.append((r, c)) q.append((r, c)) for r, c in nomis: board[r][.. 2023. 8. 24.
[Algorithm][Python]깊이/너비 우선 탐색 알고리즘(DFS/BFS) + 코드 너무 중요한 알고리즘이죠. 대표적인 그래프 탐색 알고리즘인 깊이 우선 탐색, 너비 우선 탐색에 대해서 알아봅시다. 이 그래프를 기본으로 해서 알아보겠습니다. 깊이 우선 탐색(Depth First Search) 먼저 알아볼 것은 깊이 우선 탐색, DFS 입니다. 이번 포스팅에서는 기본 그래프를 트리로 사용하고 있지만 트리에만 사용할 수 있는 것은 아닙니다. DFS는 이름 그대로 그래프를 탐색함에 있어서 깊이를 우선적으로 탐색하는 방법을 말합니다. DFS의 탐색 순서입니다. 1 → 2 → 4 → 5 → 3 → 6 → 7 의 순서로 탐색을 진행하는 모습을 확인할 수 있는데요. 저는 DFS를 보면서 호기심이 많은 사람이다 라고 생각했던 기억이 있습니다. 각 노드를 하나의 방이라고 보고 간선이 문이라고 한다면 깊.. 2023. 8. 12.
[BOJ][Python]2206 풀이 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline INF = 1000001 def bfs(): dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)] visited = [[0 for _ in range(m)] for _ in range(n)] visited[0][0] = 1 q = de.. 2023. 8. 9.
[BOJ][Python]1967 풀이 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline n = int(ssr()) adj_list = [[] for _ in range(n+1)] for _ in range(n-1): line = list(map(int, ssr().split())) adj_list[line[0]].append((line[1], li.. 2023. 7. 30.
[BOJ][Python]1167 풀이 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline n = int(ssr()) adj_list = [[] for _ in range(n+1)] for _ in range(n): line = list(map(int, ssr().split())) for i in range(1, len(line), 2): if line[.. 2023. 7. 30.
[BOJ][Python]1043 풀이 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def check_truth(): while q: p = q.popleft() for party in parties: if p in party[1:]: for i in party[1:]: if visited[i] == False: q.append(i) visited[i] = True n, m.. 2023. 7. 26.
[BOJ][Python]21736 풀이 https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def check_pos(): p_cnt = 0 for i in range(n): for j in range(m): if campus[i][j] == 'I': q.append((i, j)) campus[i][j] = 'X' elif campus[i][j] == 'P':.. 2023. 7. 24.
[BOJ][Python]14940 풀이 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def get_pos(): for i in range(n): for j in range(m): if board[i][j] == 2: visited[i][j] = 0 q.append((i, j, 0)) elif board[i][j] == .. 2023. 7. 22.
반응형

티스토리툴바