Loading [MathJax]/jax/output/CommonHTML/jax.js
본문 바로가기
728x90

그래프 이론

 2
[백준] 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로 기록하고, 연결된 노드를 탐색하면서 그 부모를 기록하는 과정을 반복했으며, 부모가..
[백준] 21736번 헌내기는 친구가 필요해 [Python] - 그래프 이론 N×M 크기이며 캠퍼스에서 O는 빈 공간, X는 벽, I는 도연이, P는 사람으로 주어질 때, 상하좌우로만 이동가능한 도연이가 몇 명의 사람을 만날 수 있을까? 더보기 문제 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 도연이가 다니는 대학의 캠퍼스는 N×M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x,y)에 있다면 이동할 수 있는 곳은 (x+1,y), (x,y+1), (x−1,y), (x,y−1)이다. 단, 캠퍼스의 밖으로 이동할 수는 없..

티스토리툴바