목록Algorithms/BFS and DFS (11)
from collections import defaultdict, deque def bfs(graph, start, distances, visited): q = deque([start]) visited[start] = True while q: current = q.popleft() for adj in graph[current]: if not visited[adj]: visited[adj] = True q.append(adj) distances[adj] = distances[current] + 1 def solution(n, edge): # 그래프 만들기 graph = defaultdict(list) visited = [False] * (n+1) for x, y in edge: graph[x].append..
https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net from copy import deepcopy n, m, k = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(n)] q = [list(map(int, input().split())) for _ in range(k)] dx, dy = [1,0,-1,0], [0,-1,0,1] ..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net from copy import deepcopy n = int(input()) board = [list(map(int, input().split())) for _ in range(n)] # logic 생각 # 상하좌우 이동이 아닌 맵의 방향을 바꿔가면서 한방향으로만 보내는 방식으로 생각 # 90도 회전 def rotate(b, n): nb = deepcopy(b) for..
https://www.acmicpc.net/problem/16768 16768번: Mooyo Mooyo In the example above, if $K = 3$, then there is a connected region of size at least $K$ with color 1 and also one with color 2. Once these are simultaneously removed, the board temporarily looks like this: 0000000000 0000000300 0054000300 1054500030 220000 www.acmicpc.net # Flood Fill # Flood Fill 처리한 후 어떻게 처리할 것인가 # Flood Fill # Flood Fi..
https://www.acmicpc.net/problem/5213 5213번: 과외맨 문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이 www.acmicpc.net 출처: https://rebas.kr/733 [PROJECT REBAS] 우선 주어지는 입력 데이터를 2차원 인접 행렬로 변환한다. 하나의 타일은 2 조각으로 나누어져 있으므로, 세로 N개 가로 N*2개이다. 따라서 인접 행렬을 a[N][N*2]로 선언한다. 입력 데이터를 인접 행렬에 넣을 때, 홀수 줄, 짝수 줄에 따라 다르게 넣어야 한다. 홀수 줄에서는 2*N개의 데이터를 모두 넣는다. 짝수 줄에서는 앞뒤로..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net n = int(input()) m = int(input()) adj = [[] for _ in range(n+1)] visited = [False] * (n+1) cnt = 0 for _ in range(m): x, y = map(int, input().split()) adj[x].append(y) adj[y].append(x) def dfs(now_pos): global cnt cnt += 1 v..