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

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

[BFS , DFS] 백준 빙산 2573번 with Python3 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 내 풀이 -시간초과- # BOJ 2573 - 빙산 - 시간초과 import sys sys.setrecursionlimit(100000) input = sys.stdin.readline # 상 우 하 좌 dr = [-1, 0, 1, 0] dc = [0, 1, 0, -1] def dfs_count(r, c): for m in range(4): nr = r + dr[m] nc = c + dc.. 2021. 8. 23.
[DFS] 백준 구슬 찾기 2617번 with Python3 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 문제 내 풀이 import sys input = sys.stdin.readline # recursion error 시 최대 재귀 깊이를 늘려주면 해결 될 지도? sys.setrecursionlimit(10000000) # 동빈나식 dfs def dfs(graph, v, visited): global count, ans visited[v] = True # 종료 조건 if count.. 2021. 8. 23.
[DP, BFS] 백준 2294번 동전 2 with Python3 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 정답 풀이 import sys input = sys.stdin.readline n, k = map(int, input().split()) # 동전 개수 n, 목표 금액 k원 coin = [] dp = [0 for i in range(k+1)] for i in range(n): coin.append(int(input())) for i in range(1, k+1).. 2021. 8. 21.
[BFS] 백준 3055번 탈출 with Python3 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 내 풀이 # R C / 행열 # D 고슴도치 / S 비버굴 / *물 / . 맨땅 / X 돌 from collections import deque import sys input = sys.stdin.readline row, col = map(int, input().split()) field = [] for i in range(row): field.append(list(input().rstrip())) vi.. 2021. 8. 21.
[BFS] 백준 7569번 토마토 with Python3 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 input = sys.stdin.readline # 앞 뒤 좌 우 아래 위 dx = [1, -1, 0, 0, 0, 0] dy = [0, 0, -1, 1, 0, 0] dz = [0, 0, 0, 0, -1, 1] def bfs(): while q: a, b, c = q.popleft() #.. 2021. 8. 20.
[DFS]백준 1987번 알파벳 with Python3 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 내 풀이 from collections import deque import sys sys.setrecursionlimit(10000) input = sys.stdin.readline rr, cc = map(int, input().split()) alpha = [] str1 = '' for _ in range(rr): str = input().rstrip() # str1 = str1 +.. 2021. 8. 20.
[BFS] 백준 2178번 미로 탐색 with Python3 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 내 풀이 from collections import deque n, m = map(int, input().split()) # maze = [list(input()) for _ in range(n)] maze = [] for i in range(n): maze.append(list(map(int, input()))) visited = [[0] * (m) for _ in range(n)] # 상 우 하 좌 dx = [-1, 0.. 2021. 8. 20.
[DFS] 백준 2606번 바이러스 with Python3 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 내 풀이 def dfs(v): visited[v] = 1 for i in range(1, n + 1): if visited[i] == 0 and graph[v][i] == 1: # 1. 방문한 적이 없고, # 2. 현재 v 노드에서 i노드로 간선이 연결되어있다면 dfs(i) n = int(input()) m = int(input()) graph = [[0] * (n + 1) for _ in ran.. 2021. 8. 20.
[DFS, BFS] 백준 1260번 DFS와 BFS with Python3 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 내 풀이 from collections import deque def bfs(start): que = deque([start]) visit_list[start] = 1 while que: vv = que.popleft() print(vv, end=' ') for i in range(1, n+1): if visit_list[i] == 0 and graph[.. 2021. 8. 20.

티스토리툴바