본문 바로가기
  • 초부득3 - 어제보다 나은 내일을 위해
  • 꿈이 현실이 되는 날까지

sw사관학교 정글 2기/03 DFS, BFS, 위상정렬18

[BFS] 백준 이분 그래프 1707번 with Python3 ★ https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 정답 풀이 ### bfs import collections import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline for _ in range(int(input())): V, E = map(int, input().split()) graph = [[] for i in range(V+1)] # 빈 그래프 생성 visi.. 2021. 8. 25.
[DFS, DP] 백준 내리막길 1520번 with Python3 ★★ https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 정답 풀이 import sys input = sys.stdin.readline sys.setrecursionlimit(10000) dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] def dfs(x, y): if x == 0 and y == 0: return 1 if dp[x][y] == -1: dp[x][y] = 0 for i in range(4): nx = x + dx.. 2021. 8. 25.
[위상정렬] 백준 음악프로그램 2623번 with Python3 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 내 풀이 from collections import deque import sys input = sys.stdin.readline # 입력 n: 가수 수 m:보조 pd 수 n, m = map(int, input().split()) # 앞 원소에서 뒷 원소를 향하는 간선들 / 진출 방향 routes = [] for _ in range(m): m_countdown = list.. 2021. 8. 25.
[BFS] 백준 섬의 개수 2588번 with Python3 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 내 풀이 import sys from collections import deque input = sys.stdin.readline # 상 우 하 좌 좌상 좌하 우상 우하 dx = [-1, 0, 1, 0, -1, 1, -1, 1] dy = [0, 1, 0, -1, -1, -1, 1, 1] def bfs_2d(r, c): que = deque([]) que.append([r, c]) vis.. 2021. 8. 25.
[BFS] 백준 단지번호붙이기 2667번 with Python3 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 내 풀이 import sys from collections import deque input = sys.stdin.readline # 입력 n = int(input()) gangnam = [list(map(int, list(input().rstrip()))) for _ in range(n)] visited = [[0] * (n) for _ in range(n)] ans = [] # 상 우 하 .. 2021. 8. 25.
[BFS] 백준 숨바꼭질 1697번 with Python3 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 내 풀이 import sys from collections import deque input = sys.stdin.readline def bfs(): while que: now = que.popleft() if now == sister: print(record[now]) exit() if 0 2021. 8. 25.
[위상정렬] 백준 작업 2056번 with Python3 ★★★ https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 정답 풀이 import sys from collections import deque def topological(): q = deque() # 진입 차수가 0인 값 q에 삽입 for i in range(1, n + 1): if len(indegree[i]) == 0: q.append((i, time[i])) # 각 작업번호i에 걸리는 시간 time[i] print(q) total =.. 2021. 8. 25.
[BFS] 백준 숨바꼭질 1697번 with Python3 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 내 풀이 import sys from collections import deque input = sys.stdin.readline def bfs(): while que: now = que.popleft() if now == sister: print(record[now]) exit() if 0 2021. 8. 24.
[위상정렬] 백준 장난감 찾기 2637번 with Python3 ★★ https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 문제 정답 풀이 import sys from collections import deque input = sys.stdin.readline # N = 완제품 번호, 1,2,3,...N-1 까지 기본부품 혹은 중간부품 N = int(input().rstrip()) # M = 어떤 부품을 완성하는데 필요한 부품들의 관계 개수 M = int(input().rstrip()) ar.. 2021. 8. 24.

티스토리툴바