그래프탐색

[baekjoon 11725] 트리의 부모 찾기- 트리, 그래프, BFS, DFS (C++)

www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 루트는 1로 고정되어있고, 각 노드들의 부모를 출력하면 되는 문제이다. 일단 벡터를 통해 양 노드의 값을 저장해주고, DFS탐색을 노드 1부터 해준다. 트리의 특성상 리프 노드를 제외하고 연결되어 있으므로 연결된 노드를 통해 탐색해주면서, 부모를 저장해준다. 현재 x노드를 방문한 상태에서 x와 연결된 y가 아직 방문되지 않았다는 것은 y는 x의 자식 노드라는 의미이다. 방문하지 않았다면 DFS(연결된 다음 노드)를 진행해주면서 parent [연결된 다음 노드] = 현재 노드..

[baekjoon 14502] 연구소 - 그래프탐색(BFS,DFS), 브루트포스

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 기본적인 그래프 탐색에 벽을 쌓아야하는 경우를 생각해야하는 문제이다. 처음에 문제를 읽고 무작위 벽 3개를 어떤 로직을 통해 세워야할까, 고민을 하다가 입력값의 최대 배열 크기가 8x8 인것을 보고 브루트포스로 모든 경우를 탐색해보면 되겠다고 생각을 했다. 벽을 세우는 케이스는 크게 두가지 인 것 같다. 1. 그래프를 입력받을 때 벽도 없고, 바이러스도 없는 x,y 좌표값을 따로 vector에 보관해두고 이 벡터에서 3가지..

[baekjoon 2468] 안전영역 - 그래프탐색(BFS, DFS)

www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 기본적으로 배열에 데이터를 받아서 그래프 탐색을 수행하는 문제였다. 다만 문제 마지막 조건에 아무 지역도 물에 잠기지 않을 수 있다는 조건으로 바로 맞추진 못했다.. #include #include using namespace std; int bound[101][101], N, height, resultMax, xmove[4] = { 1, -1, 0, 0 }, ymove[4] = { 0, 0, 1, -1 }; bool..