dfs 6 썸네일형 리스트형 [백준] 11725번 트리의 부모 찾기 [Python] - 그래프 이론, BFS, DFS 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 문제 더보기 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2≤N≤100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. https://www.acmicpc.net/problem/11725 bfs나 dfs 알고리즘을 사용해서 1의 자식을 탐색하면서 그 자식의 부모를 1로 기록하고, 연결된 노드를 탐색하면서 그 부모를 기록하는 과정을 반복했으며, 부모가.. [백준] 14500번 테트로미노 [Python] - BFS, DFS N x M 개의 숫자가 주어짐 위와 같은 정사각형 4개를 이어붙인 도형 하나를 주어진 N x M 크기의 종이 위에 올렸을 때, 도형이 덮는 칸의 수들의 합의 최댓값을 구하는 문제 더보기 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노.. [백준] 11403번 경로 찾기 [Python] - DFS, BFS, 플로이드–워셜 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i,j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 문제 플로이드–워셜, dfs, bfs를 사용한 코드들을 작성해봤습니다. 더보기 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i,j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1≤N≤100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제.. [백준] 2667번 단지번호붙이기 [Python] - DFS, BFS NxN 지도에 1은 집이 있는 곳, 0은 집이 없는 곳을 나타냄 상하좌우로 연결된 집의 모임을 단지라고 함 단지의 개수와 각 단지별 집의 수를 오름차순으로 정렬해 출력하는 문제 더보기 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(.. [백준] 2606번 바이러스 [Python] - DFS, BFS 1번 컴퓨터가 바이러스에 감염됨 연결된 컴퓨터는 바이러스를 전파함 1번에 의해 감염될 모든 컴퓨터의 개수를 구하는 문제 (개수에 1번은 제외,,,) 더보기 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1.. [백준] 1260번 DFS와 BFS [Python] - DFS, BFS 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제 더보기 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N1≤N≤1,000, 간선의 개수 M1≤M≤10,000, 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 B.. 이전 1 다음
