BFS, DFS

백준 2606 바이러스

n = int(input()) # 사람수
pair = int(input()) # 페어수

visited = [False] * 101 # 최대 100개의 노드이므로 100+1
graph = [[] for _ in range(101)]

for _ in range(pair):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a) # 각자 노드 입장에서 연결된 노드들 다 추가


from collections import deque
def bfs(start):
    if not visited[start]:
        visited[start] = True
        queue = deque([start]) # 맨처음 노드만 여기를 거쳐간다

    while queue:
        present = queue.popleft()
        visited[present] = True
        if graph[present]:
        #여기선 SORT할필요없지만 순회할 때 작은 순서대로 돈다면 아래처럼
            for i in sorted(graph[present]): 
                if not visited[i]:
                    queue.append(i)

bfs(1)
print(sum(visited)-1) # 자기자신을 빼고

1. 쉬운 문제였다. BFS로 순회하고나서 visited 처리된 노드 개수를 출력하면 됐다.

1249 SWEA 보급로

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

from collections import deque
def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 지도를 벗어난 경우
            if nx < 0 or nx >(n-1) or ny < 0 or ny >(n-1):
                continue

            # 만약 현재 계산한 비용이 원래 계산해놓은 비용보다 적다면 갱신
            if cost_save[x][y] + grid[nx][ny] < cost_save[nx][ny]:
                queue.append((nx, ny))
                cost_save[nx][ny] = cost_save[x][y] + grid[nx][ny]

case = int(input())
for i in range(case):
    n = int(input()) # 지도 크기
    grid = []
    cost_save = [[99999 for _ in range(n)] for _ in range(n)]
    cost_save[0][0] = 0
    for _ in range(n):
        grid.append(list(map(int, list(input())))) # 깊이는 9이하이다. 아마...
    bfs(0,0)
    print('#{} {}'.format(i+1, cost_save[n-1][n-1]))

bfs해야한다는 건 알겠는데 모든 경우를 따져봤을 때 비용이 적게 되는 것을 어떻게 찾을 지는 도저히 모르겠었다.
그래서 요기을 참고했다.

가는데 드는 비용을 따로 저장해둘 어레이만들고
각 단계에서 저장되어있는 비용보다 적게 드는 경로가 있다면 그 경로로 탐색하는 것이 아이디어이다.