시나위

www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net import sys input = sys.stdin.readline from collections import deque K = int(input()) for tc in range(K): V, E = map(int, input().split()) # 인접 리스트 link_arr = [list() for _ in range(V + 1)] for _ in range(E): n1, n2 = map(int..

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split()) matrix = [input() for _ in range(N)] visit = [[0] * M for _ in range(N)] def bfs(r, c): q = deque() q.append((r, c)) visit[r][c] = 1 delta = [(-1, 0..

www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net from collections import deque delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] def bfs(q): man_move = 1 while q: x, y, z = q.popleft() if z == 0 and (x == 0 or x == h - 1 or y == 0 or y == w - 1): return visit[x][y][0] if z == 0: man_move -= 1 ..

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net import sys sys.stdin = open('2206_input.txt','r') from collections import deque n, m = map(int, input().split()) matrix = [input() for _ in range(n)] visit = [[(-1, True)] * m for _ in range(n)] visit[0][0] = (1, True..

www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net import sys input = sys.stdin.readline from collections import deque delta = [(-2, -1), (-2, 1), (2, -1),(2, 1), (-1, -2), (-1, 2), (1, -2),(1, 2)] for tc in range(int(input())): n = int(input()) matrix = [[-1] * n for _ in range(n)]..

www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net from collections import deque n, k = map(int, input().split()) if n == k: print(0) print(1) else: dp = [0] * 100001 q = deque([n]) dp[n] = 1 size, depth, cnt = len(q), 0, 0 if_chk = True limit = 100000 result_v..

www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net from collections import deque def bfs(queue): visited = [0] * (n + 1) visited[queue[0]] = 1 while queue: x = queue.popleft() for adjacent in link_dict[x]: if visited[adjacent]: continue queue.append(adjacent) visited[adjacent] = vi..

https://acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net from collections import deque def bfs(q): melting = 0 melt_list = set() while q: x, y = q.popleft() for i in range(4): dx = x + delta[i][0] dy = y + delta[i][1] if dx = h + 2 or dy = w + 2: continue if visited[dx][dy]: continue..

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXWXMZta-PsDFAST&categoryId=AXWXMZta-PsDFAST&categoryType=CODE&problemTitle=10966 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com from collections import deque for tc in range(1, int(input()) + 1): n, m = map(int, input().split()) visited = [[-1] * m for _ in range(n)] _map = [] q = deque() for i..

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE&problemTitle=1953 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com from collections import deque tunnel = { 1: [(-1, 0), (1, 0), (0, -1), (0, 1)], # 상하좌우 2: [(-1, 0), (1, 0)], # 상하 3: [(0, -1), (0, 1)], # 좌우 4: [(-1, 0), (0, 1)], # 상우 ..