1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 코드 from collections import deque n, m = map(int, input().split()) board = [input() for _ in range(m)] visited = [[False]*n for _ in range(m)] power = {"W": 0, "B": 0} # 각 나라의 병사의 위력의 합 def bfs(x, y, color): dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] q..
그래프탐색
17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 코드 from collections import deque n, m, x = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b = map(int, input().split()) # a가 b보다 잘함 graph[a].append((b, 1)) graph[b].append((a, -1)) def bfs(st..
1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 코드 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) maze = [] points = [] for i in range(n): row = list(input()) maze.append(row) for j in range(n): if row[j] == 'S' or row[j] == 'K': maze[i]..
11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 코드 from collections import deque import sys input = sys.stdin.readline n = int(input()) graph = [[] for _ in range(n+1)] # 노드 간 연결 for _ in range(n-1): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) # 각 노드 레벨 구하기(BFS) level = [-1]*(n+..
14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 코드 from collections import deque import sys input = sys.stdin.readline dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] n, m = map(int, input().split()) hx, hy = map(int, input().split()) ex, ey = map(int, input().split()) maze = [list(map(int, input().split()))..
