[백준 / C++] 7569번: 토마토 (BFS, 3차원 배열)

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 난이도: solved.ac 골드 5 box라는 3차원 배열을 만들고, 해당 배열에 입력을 받았다. 그리고 먼저 box[i][j][k] = 1인 곳을 큐에 담고, 큐에서 하나씩 꺼내 주위 위, 아래, 오른쪽, 왼쪽, 앞, 뒤 중 0인 곳은 값을 1씩 증가시켜 저장하였다. 0일차를 1로 시작했으므로 box[i][j][k]가 가장 큰 곳에서 1을 뺀 값을 출력하도록 해주었다. 그..

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

[백준 / C++] 2644번: 촌수계산 (BFS 풀이)

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 난이도: solved.ac 실버 2 알고리즘 분류 그래프 탐색(BFS, DFS) 접근 방법 input에서 두 번째 줄에 주어지는 두 사람을 각각 a, b라고 하고, a 노드부터 시작해 BFS를 이용하여 한 칸씩 이동한다 이때 각 노드의 방문 여부를 알려주는 visited에 촌수 + 1을 적는다 (Ex. a와 i가 3촌이면 visited[i] = 4) 코드 #include #in..

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

[백준 / C언어] 14940번: 쉬운 최단거리 (BFS)

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 및 구현 목표 지점인 2부터 BFS을 시작해서 목표 지점까지의 거리가 몇 인지 visited에 적어준다. BFS 탐색을 끝내고 나서는 map = 0(= 갈 수 없는 땅)이 아니면서 visited가 0인 지점은 도달하지 못하는 곳을 의미하므로 해당 부분의 visited는 ..

• 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언어] 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