풀이특징
range(시작점, 시작점+길이)
인덱스를 통해 풀 수 있다.itertools
import permutations
from itertools import permutations
# 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최솟값을 반환
def solution(n, weak, dist):
# 취약 지점 개수
weakSize = len(weak)
# 원형을 길이 2배로 늘린 일자형태로 변형
weak = weak + [w + n for w in weak]
# 투입할 친구수 초기값은 친구수+1
minCount = len(dist) + 1
# 취약지점 시작점
for weakStart in range(weakSize):
# 친구들 순서나열
for friends in permutations(dist, len(dist)):
# 투입할 친구수
count = 1
# 점검할 수 있는 마지막 위치 = 취약지점 + 가능길이
endPoint = weak[weakStart] + friends[count-1]
# 취약지점을 돌면서 확인
for i in range(0, weakSize):
index = weakStart + i
# 범위를 벗어난 경우
if weak[index] > endPoint:
# 새로운 친구 투입
count += 1
# 더 투입이 불가한 경우 종료
if count > len(dist):
break
# 점검할 수 있는 마지막 위치 = 현재 취약지점 + 가능 길이 업데이트
endPoint = weak[index] + friends[count-1]
# 원을 전부 확인한 경우 최소값 업데이트
minCount = min(minCount, count)
# 모든 친구 투입에도 불가한 경우
if minCount > len(dist):
return -1
return minCount
풀이특징
from collections import deque
# x로부터 출발하여 최단 거리가 정확히 k인 모든 도시의 번호를 출력
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
graph[a-1].append(b-1)
distance = [0] * n
q = deque([x-1])
results = []
while q:
now = q.popleft()
for node in graph[now]:
if distance[node] == 0:
q.append(node)
distance[node] = distance[now]+1
if distance[node] == k:
results.append(node)
results.sort()
if len(results) == 0:
print(-1)
else:
for i in results:
print(i+1)
풀이특징
# 안전 영역 크기의 최댓값 출력
# 0: 빈칸, 1: 벽, 2: 바이러스
from itertools import combinations
from collections import deque
import copy
moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]
n, m = map(int, input().split())
graph = []
empty = []
virus = []
for x in range(n):
row = list(map(int, input().split()))
graph.append(row)
for y in range(m):
if row[y] == 0:
empty.append((x, y))
elif row[y] == 2:
virus.append((x, y))
# 안전 영역의 크기
safeCount = 0
# 바이러스 DFS 함수
def bfs(graph, emptyCount, virus):
q = deque(virus)
while q:
x, y = q.popleft()
for move in moves:
nextX, nextY = x+move[0], y+move[1]
if nextX < 0 or nextX >= n:
continue
if nextY < 0 or nextY >= m:
continue
# 빈칸인 경우 바이러스 퍼짐
if graph[nextX][nextY] == 0:
graph[nextX][nextY] = 2
emptyCount -= 1
q.append((nextX, nextY))
return emptyCount
# 빈칸 세곳을 조합으로 선택 -> 벽 설정
for case in combinations(empty, 3):
checkGraph = copy.deepcopy(graph)
for x, y in case:
checkGraph[x][y] = 1
# 남은 빈칸수
emptyCount = len(empty)-3
# 바이러스 BFS 진행 후
safe = bfs(checkGraph, emptyCount, virus)
safeCount = max(safeCount, safe)
print(safeCount)
# s초가 지난 후에 x, y에 존재하는 바이러스의 종류를 출력
from collections import deque
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
n, k = map(int, input().split())
graph = []
virus = []
for i in range(n):
graph.append(list(map(int, input().split())))
for j in range(n):
if graph[i][j] != 0:
virus.append((graph[i][j], 0, i, j))
s, x, y = map(int, input().split())
virus.sort()
q = deque(virus)
while q:
v, time, i, j = q.popleft()
if time == s:
break
for move in moves:
nextX, nextY = i+move[0], j+move[1]
if nextX < 0 or nextX >= n:
continue
if nextY < 0 or nextY >= n:
continue
if graph[nextX][nextY] == 0:
graph[nextX][nextY] = v
q.append((v, time+1, nextX, nextY))
print(graph[x-1][y-1])