DFS3 [백준] 2606번 바이러스 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/2606 난이도 낮은 개념 공부용 문제이다. [문제] 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 .. 2023. 1. 30. BFS - 미로 탈출 [문제] N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. [입력] 첫째 줄에 두 정수 N, M(4 2023. 1. 19. DFS 이론 DFS(깊이 우선 탐색)은 그래프의 깊은 부분부터 탐색하는 알고리즘이다. DFS는 스택 자료구조나 재귀함수를 이용한다. 다음과 같은 과정으로 동작한다. 한 번 방문한 노드는 다시 방문하지 않으므로, 보통은 방문처리 리스트를 만들어 그 안에 False인지 True인지를 체크하는 방식으로 방문 여부를 파악한다. 스택에 시작 노드를 넣고 방문처리한다. 스택의 최상단 노드에 연결된 노드 중, 아직 방문하지 않은 노드가 있다면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 노드가 없다면 그 최상단 노드를 꺼낸다. 스택에 아무 것도 없을 때 까지(혹은 문제에서 주어진 답을 풀 때 까지?) 반복한다. 위와 같은 그래프가 있고, 시작노드는 1이며, 번호가 낮은 인접노드부터 방문한다고 하자. 시작노드인 1을 방문처.. 2023. 1. 17. 이전 1 다음
