[백준 / C++] 1068번: 트리 (DFS)

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 그래프 탐색 (DFS) 구현 방법 부모 노드의 번호를 index로 갖는 벡터에 해당 자식 노드의 번호를 저장한다. (Ex. 4번 노드의 부모가 2면, graph[2].push_back(4)) 그리고 삭제할 노드의 번호를 입력받는데, 삭제할 노드가 루트 노드라면 트리는 아예 없어지므로 0을 출력하게 한다. 삭제할 노드가 루트 노드가 아니라면 D..

• format_list_bulleted PS/백준
• · 2023. 8. 6.
• textsms

[백준 / C++] 1987번: 알파벳 (DFS)

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (DFS) 접근 방법 및 구현 맨 왼쪽 위 알파벳부터 DFS를 돌리면 된다. 방문한 알파벳을 표시하기 위해서 알파벳은 총 26개이므로 26칸짜리 배열 visited를 선언해 A부터 Z까지 index = 0 ~ 25을 갖도록 해주었다. 따라서 인접한 상하좌우의 알파벳을 방문했는지 O(1)에 체크할 수 있다. 코드 #include ..

• format_list_bulleted PS/백준
• · 2023. 8. 4.
• textsms

[백준 / C언어] 2617번: 구슬 찾기 (DFS 풀이)

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (DFS) 접근 방법 및 구현 무게가 중간이 될 수 없는 구슬은 해당 구슬보다 더 가볍거나 무거운 구슬의 개수가 N / 2개보다 많아야 한다. 더 가볍거나 무거운 구슬의 개수는 DFS를 이용해 구할 수 있다. 입력으로 들어오는 구슬의 관계는 2차원 배열을 이용해 방향그래프로 나타내었다. 아래와 같은 입력이 주어진다고 ..

• format_list_bulleted PS/백준
• · 2023. 7. 8.
• textsms

[백준 / C언어] 11724번: 연결 요소의 개수 (DFS로 풀이)

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 난이도: solved.ac 실버 2 알고리즘 분류 그래프 탐색, DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 구현 노드를 방문하면 visited에서 해당 노드의 값을 1로 바꾸고, 해당 노드와 연결된 다른 노드로 DFS 함수를 통해 탐색하였다. 그리고 더 이상 연결된 노드가 없을 때까지 DFS 함수를 재귀호출하도록 하였다. 연..

• format_list_bulleted PS/백준
• · 2023. 7. 2.
• textsms

[백준 / C언어] 2668번: 숫자고르기 (DFS로 풀이)

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 그래프 탐색, DFS (깊이 우선 탐색) 접근 방법 방향이 있는 그래프로 생각하면 쉽다. 사이클이 있는 노드들의 개수를 세는 문제다. 문제에 있는 표에서 1행의 숫자들을 노드라고 생각하고, 2행에 있는 숫자들을 1행에 있는 노드에서 연결된 노드라고 보면 된다. 구현 1번 노드부터 N번 노드까지 각 노드를 시작점으로 해서 화살표를 따라가..

• format_list_bulleted PS/백준
• · 2023. 6. 29.
• textsms

[백준 / C언어] 1926번: 그림 (DFS로 구현)

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그래프 탐색 (DFS, BFS) 구현 방법 나는 DFS로 풀어보았다 입력을 다 받은 뒤에는 2중 for 문으로 1인 위치(그림이 있는 위치)를 찾아주고 그 위치를 초기 기점으로 해서 DFS를 돌렸다 DFS 함수로 들어가기 전에 그림의 개수를 파악할 용도로 사용한 int형 변수 print를 1 증가시켜 주었다 DFS 함수 내에서는 방문할 때마다 그림의 사..

• format_list_bulleted PS/백준
• · 2023. 5. 29.
• textsms