본문 바로가기
반응형

알고리즘/그래프 탐색12

[백준][Python] 1446번 지름길 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 코드 n, d = map(int,input().split()) n_list = [list(map(int,input().split())) for _ in range(n)] graph = [i for i in range(d+1)] for i in range(d+1): graph[i] = min(graph[i],graph[i-1]+1) for start,end,le in n_list: if i == start and end 2022. 12. 30.
[백준][Python] 1743번 음식물 피하기 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 코드 from collections import deque def bfs(x,y): global cnt queue = deque() queue.append((x,y)) while queue: x,y = queue.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] if 1 2022. 12. 20.
[백준][Python] 2583번 영역 구하기 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 코드 import sys sys.setrecursionlimit(10000) from collections import deque def bfs(x,y): global cnt queue = deque() queue.append((x,y)) while queue: x,y = queue.popleft() rec[x][y] = 1 for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 2022. 12. 1.
[백준][Python] 10026번 적록색약 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 코드 from collections import deque import sys sys.setrecursionlimit(10000) def bfs(x,y): queue = deque() queue.append((x,y)) while queue: x,y = queue.popleft() visit[x][y] = True color = graph[x][y] for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 2022. 11. 29.
반응형

티스토리툴바