본문 바로가기
반응형

Problem Solving/DFS, BFS26

[DFS, BFS] 백준 3055번: 탈출 / 골드 5 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net import collections x_lim, y_lim = map(int, input().split()) graph = [] visit = [] start = [] target = [] for x in range(x_lim): row = [x for x in input()] graph.append(row) visit.append([False]*len(row)) for y in range(len(row)): .. 2021. 7. 20.
[DFS, BFS] 백준 13913번: 숨바꼭질 4 / 골드 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net import collections n, k = map(int, input().split()) count = 0 visit = [False]*(100000+1) prev = {} if n == k: print(0) print(n) quit() def makeOrder(pos): ord = [pos] cur = pos while cur != n: ord.append(.. 2021. 7. 16.
[DFS, BFS] 백준 2583번: 영역 구하기 / 실버1 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net import sys sys.setrecursionlimit(15000) y_lim, x_lim, n = map(int,input().split()) graph = [] for i in range(x_lim): graph.append([0]*y_lim) for i in range(n): x1, y1, x2, y2 = map(int,input().split()) for j in r.. 2021. 5. 31.
[DFS, BFS] 백준 1987번: 알파벳 *** / 골드4 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net x_lim, y_lim = map(int, input().split()) graph = [] for i in range(x_lim): graph.append(input()) dx = [-1,1,0,0] dy = [0,0,-1,1] def dfs(x,y,count, visited): global answer if graph[x][y] in visited: answer = max(answer,.. 2021. 5. 31.
[DFS, BFS] 백준 2468번: 안전 영역 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net import sys import copy sys.setrecursionlimit(15000) n = int(input()) max_num = -sys.maxsize min_num = sys.maxsize graph = [] for i in range(n): lst = list(map(int,input().split())) graph.append(lst) max_num = max(max_num, max(l.. 2021. 5. 30.
[DFS, BFS] 백준 11403번: 경로 찾기 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net import collections n = int(input()) graph = collections.defaultdict(list) for i in range(n): edges = list(map(int, input().split())) for j in range(len(edges)): if edges[j] == 1: graph[i].append(j) def dfs(node): if node in discovered: return disc.. 2021. 5. 29.
반응형

티스토리툴바