공부 기록

✏️ 문제 문제 파악처음 바이러스에 걸린 컴퓨터와 인접된 모든 컴퓨터를 돌아야 하므로 BFS가 아닌 DFS를 사용해서 풀어야 한다. # 1graph = [[0] * (c+1)] * (c+1) graph[1][2] = 1print(graph)# [[0, 0, 1, 0],# [0, 0, 1, 0],# [0, 0, 1, 0],# [0, 0, 1, 0]]# 2graph = [[0] * (c+1) for _ in range(c+1)]graph[1][2] = 1print(graph)# [[0, 0, 0, 0],# [0, 0, 1, 0],# [0, 0, 0, 0],# [0, 0, 0, 0]] 처음 graph 2차원 배열을 초기화할 때 # 1 과 같이했는데 원하는 값이 계속 안나왔다.  찾아보니 # 1 과 ..

✏️ 문제 문제 파악최소의 칸 수를 출력하기 원하므로 전체 경로를 탐색하는 DFS가 아닌 BFS를 사용해야 한다. 또한 상하좌우로 움직일 수 있으므로 상하좌우 하나하나 움직이며 움직인 좌표가 이동할 수 있는 칸인 지, 이미 방문했던 칸은 아닌 지 확인하는 것이 포인트이다. 처음에는 단순히 지나간 칸마다 cnt += 1을 해서 cnt 값을 출력하는 방식으로 문제를 풀었다. 그런데 생각해보니 지나간 칸이더라도 그 이후에 갈 수 있는 경로가 없다면 그 칸을 문제에서 요구하는 최소 칸 수에 포함시키면 안 된다. 그래서 이전의 방문한 칸에 이때까지 지나왔던 칸의 수를 1씩 더하니 답이 나왔다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드import sysinput = sys.stdin.readlinefr..