[이코테] 구현문제 정리

A15_특정 거리의 도시 찾기

from collections import deque

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
	a, b = map(int, input().split())
    graph[a].append(b)
    
distance = [-1] * (n + 1)
distance[x] = 0

q = deque([x])
while q:
	now = q.popleft()
    for next_node in graph[now]:
    	if distance[next_node] == -1:
        	distance[next_node] = distance[now] + 1
            q.append(next_node)
            
check = False
for i in range(1, n+1):
	if distance[i] == k:
    	print(i)
        check = True
        
if check == False:
	print(-1)

A16_연구소

n, m = map(int, input().split())
data = []
temp = [[0] * m for _ in range(n)]

for _ in range(n):
	data.append(list(map(int, input().split())))
    
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

def virus(x, y):
	for i in range(4):
    	nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
        	if temp[nx][ny] == 0:
            	temp[nx][ny] = 2
                virus(nx, ny)
                
def get_score():
	score = 0
    for i in range(n):
    	for j in range(m):
        	if temp[i][j] == 0:
            	score += 1
    return score
    
def dfs(count):
	global result
    if count == 3:
    	for i in range(n):
        	for j in range(m):
            	temp[i][j] = data[i][j]
        for i in range(n):
        	for j in range(m):
            	if temp[i][j] == 2:
                	virus(i, j)
        result = max(result, get_score())
        return
        
    for i in range(n):
    	for j in range(m):
        	if data[i][j] == 0:
            	data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1
                
dfs(0)
print(result)

A17_경쟁적전염

from collections import deque

n, k = map(int, input().split())

graph = []
data =[]

for i in range(n):
	graph.append(list(map(int, input().split())))
    for j in range(n):
    	if graph[i][j] != 0:
        	data.append((graph[i][j], 0, i, j))
            
data.sort()
q = deque(data)

target_s, target_x, target_y = map(int, input().split())

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


while q:
	virus, s, x, y = q.popleft()
    if s == target_s:
    	break
    for i in range(4):
    	nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 ny < n:
        	if graph[nx][ny] == 0:
            	graph[nx][ny] = virus
                q.append((virus, s + 1, nx, ny))
                
print(graph[target_x - 1][target_y - 1])