1012 유기농 배추, 1325 효율적인 해킹, 10282 해킹

 

1012 유기농 배추, 1325 효율적인 해킹, 10282 해킹

 

1012 유기농 배추

import sys
sys.setrecursionlimit(100000)

def dfs(v, w):
	visited[v][w] = True
	directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	for dx, dy in directions:
		nx, ny = v + dx, w + dy
		if nx < 0 or nx >= n or ny < 0 or ny >= m:
			continue
		if adj[nx][ny] and not visited[nx][ny]:
			dfs(nx, ny)

for _ in range(int(input())):
	m, n, k = map(int, input().split())
	visited = [[False] * m for _ in range(n)]
	adj = [[0] * m for _ in range(n)]	
	for _ in range(k):
		y, x = map(int, input().split())
		adj[x][y] = 1
	count = 0
	for i in range(n):
		for j in range(m):
			if adj[i][j] and not visited[i][j]:
				dfs(i, j)
				count += 1
	print(count)

- 행렬 만드는 코드 숙지

- 방문 체크와 행렬 값은 따로 확인해야 함

- 최솟값, 최댓값 잘 확인

- 행렬의 행과 열 자리 구별(array[x][y]에서 x : 세로, y : 가로)

 

 

1325 효율적인 해킹

from collections import deque

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

for _ in range(m):
	x, y = map(int, input().split())
	adj[y].append(x)
	
def bfs(v):
	q = deque([v])
	visited = [False] * (n+1)
	visited[v] = True
	count = 1
	while q:
		v = q.popleft()
		for e in adj[v]:
			if not visited[e]:
				q.append(e)
				visited[e] = True
				count += 1
	return count

result = []
max_value = -1

for i in range(1, n+1):
	c = bfs(i)
	if c > max_value:
		result = [i]
		max_value = c
	elif c == max_value:
		result.append(i)
		max_value = c
		
for e in result:
	print(e, end=' ') 

- bfs 반복 학습 필요..

- max값 갱신을 위해서 매번 새로운 리스트를 생성하는 게 좋은 건가..?

- 한 방향으로 갱신하는게 좀 달랐음

 

 

10282 해킹

import heapq
import sys
input = sys.stdin.readline

def dijkstra(start):
	heap_data = []
	heapq.heappush(heap_data, (0, start))
	distance[start] = 0
	while heap_data:
		dist, now = heapq.heappop(heap_data)
		if distance[now] < dist:
			continue
		for i in adj[now]:
			cost = dist + i[1]
			if distance[i[0]] > cost:
				distance[i[0]] = cost
				heapq.heappush(heap_data, (cost, i[0]))
				
for _ in range(int(input())):
	n, m, start = map(int, input().split())
	adj = [[] for i in range(n+1)]
	distance = [1e9] * (n+1)
	for _ in range(m):
		x, y , cost = map(int, input().split())
		adj[y].append((x, cost))
	dijkstra(start)
	count = 0
	max_distance = 0
	for i in distance:
		if i != 1e9:
			count += 1
			if i > max_distance:
				max_distance = i
	print(count, max_distance)

- ...

- 다익스트라 알고리즘 이해 필요