본문 바로가기
반응형

BFS25

[BOJ][Python]14501 풀이 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net from collections import deque n = int(input()) t = {n+1:(16,16)} q = deque([(1, 0)]) ans = [] for i in range(1, n+1): a, b = map(int, input().split()) t[i] = (a, b) while q: tmp = q.popleft() c, d = t[tmp[0]] if tmp[0]+c 2023. 3. 4.
[BOJ][Python]16953번 풀이 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net from collections import deque a,b = map(int, input().split()) q = deque([(a,0)]) ans = -1 while q: tmp = q.popleft() if tmp[0] == b: ans = tmp[1]+1 break val1, val2 = tmp[0]*2, int(str(tmp[0])+'1') if val1 2022. 7. 25.
[BOJ][Python]11725번 풀이 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline sys.setrecursionlimit(10**7) def dfs(parent): if visited[parent] == 1: return visited[parent] = 1 for i in adjacency_list[parent]: if visited[i] == 0: ans[i] = parent dfs(i) def bfs(): tmp = so.. 2022. 7. 22.
[BOJ][Python]16236번 풀이 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def bfs():#n^2 - 1 돌면서 현재 상태에서 먹을 수 있는 물고기를 전부 추가 visited = [[0 for _ in range(n)] for _ in range(n)] while q: tmp = q.popleft() visited[tmp[0]][tmp[1]] .. 2022. 7. 17.
[BOJ][Python]9019번 풀이 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net from collections import deque import sys input = sys.stdin.readline t = int(input()) for _ in range(t): a,b = input().split() b = '0'*(4-len(b)) + b visited = [0 for _ in range(10000)] q = deque([(a,'')]) visited[int.. 2022. 7. 14.
[BOJ][Python]16928번 풀이 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline n,m = map(int, ssr().split()) ls = [list(map(int, ssr().split())) for _ in range(n+m)] visited = [0 for _ in range(101)] q=deque([(.. 2022. 7. 13.
[BOJ][Python]10026번 풀이 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def sol(): for i in range(n): for j in range(n): if visited[i][j] == 0: q.append((i,j)) visited[i][j] = 1 c = t[i][j] while q: tmp = q.popleft() for k in.. 2022. 7. 11.
[BOJ][Python]7569번 풀이 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline m,n,h = map(int, ssr().split()) t = [[list(map(int, ssr().split())) for _ in range(n)] for _ in range(h)] q = deque([]) dp=[(-1,0,0), (1,0,0), (.. 2022. 7. 10.
[BOJ][Python]2667번 풀이 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def sol(): global num while q: r,c = q.popleft() for i in range(4): if 0 2022. 7. 4.
[BOJ][Python]2178번 풀이 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def sol(): while q: r,c,s = q.popleft() if r == n-1 and c == m-1: return s for i in range(4): if r+dr[i] = n or c+dc[i] = m: continue else: if t[r+dr[i]][c+dc[.. 2022. 7. 2.
반응형

티스토리툴바