결국 빛나리라

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net > dfs 활용 연결되어있는 격자들에 방문처리하고 개수를 카운트한다는 점에서 dfs 알고리즘을 사용하였다. 먼저 격자 정보들을 2차원 배열형태로 입력한다. 아래 코드로 값을 입력받으면 숫자들이 모두 문자형태로 들어간다는 것을 기억하자. 그리고 격자에 방문했는지 여부를 보여주는 visited 배열과 격자의 상하좌우로 움직이기 위한 dx, dy 배열도 선언해준다. 행, 열 정보를 파라미터로 넣은 dfs..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net > dfs 활용 단방향 그래프가 아닌 양방향 그래프임에 주의해야한다. ▷ 처음에는 단방향 그래프로 다음과 같이 구현했다. 그러나 위 코드는 다음과 같은 예제는 풀지 못한다. 위와 같은 그래프가 있다고 할때 단방향 그래프는 1번 노드에서 출발했을 때 3번과 2번노드와 연결되어 있다고 인식하기 때문에 다음과 같이 1과 연결된 노드의 수로 2를 출력한다. ▷ 그러나 문제에 따르면 1번 노드는 2,3번 노드 ..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ DFS (Depth-First Search) 란? 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 시작노드에서 시작하여 인접한 노드들을 방문하며 가장 깊숙이 위치하는 노드에 닿을 때까지 탐색한다. 인접한 리스트가 여러개일 경우 노드의 숫자가 가장 낮은 방향으로 탐색한다. > 다음 그래프가 있을 때 DFS는 어떤식으로 탐색할까? (설명 뒤의 []는 쌓이는 스택을 표현한 것이다) - 1에서 탐색을 시작한다. [1] - 연결된 노드 2,8,6중 가장 낮은 수인 2로 탐색한다. [1,2] - 2에서 3으로 방문한다. [1..