[백준 / 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언어] 7562번: 나이트의 이동 (BFS 풀이)

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 최소 이동 횟수를 구하는 문제이므로 BFS로 접근하였다. 구현 위의 그림처럼 1시 방향부터 시작해 11시 방향까지 시계 방향으로 이동시키는 것을 한 단계로 큐에 넣어주었다. 방문한 좌표는 visited에 몇 번째로 이동한 건지 적어주었다. 코드 #define _CRT_SECURE_NO_WARNINGS #include..

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

[백준 / C언어] 1697번: 숨바꼭질 (BFS 풀이)

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그래프 탐색 (BFS) 구현 방법 수빈이의 위치와 이동 횟수(찾는 시간)를 저장할 구조체 LOC를 만들어주었다. BFS에서 사용할 큐는 LOC형 배열로 만들어주었고 index는 100001까지로 해주었다. 내 풀이에서 주목해야 할 점이 있는데 -1 만큼 이동할 때 loc가 0보다 작아지면 안 되는 것이고, +1 만큼 이동..

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

[백준 / C언어] 17070번: 파이프 옮기기 1 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 다이나믹 프로그래밍 (dp), 그래프 탐색 (DFS) 접근 방법 각 칸 별로 옮길 수 있는 방법의 수가 정해져 있으므로 dp를 이용해 풀어야겠다고 생각했다. 파이프를 옮겼을 때 가로 상태이려면 이전 상태가 가로 또는 대각선 상태여야 한다. 그리고 대각선 상태라면 이전 상태가 가로 또는 대각선 또는 세로 상태여야 하고, 세로..

• format_list_bulleted PS/백준
• · 2023. 6. 30.
• 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언어] 2468번: 안전 영역 (BFS로 풀이)

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 BFS, DFS (그래프 탐색) 접근 방법 각 영역의 높이를 입력 받을 때 해당 높이를 따로 기억하여 높이가 1일 때부터 100일 때까지 중 입력 받은 높이일 때만 전체 영역을 BFS로 탐색한다. 모든 경우에서 안전 영역의 개수가 가장 많을 때를 저장해 출력한다. 구현 높이 배열 arr_h를 만들어, 각 지역의 높이를 입력받을 때 해당 높이의 index ..

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