C++ / 1926 / 그림 ( 깊이 우선 탐색 )

https://www.acmicpc.net/problem/1926문제 요약어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넒이가 가장 넒은 것의 넓이를 출력해야합니다.단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의합니다.가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림입니다. 그림의 넓이란 그림에 포함된 1의 개수 입니다.문제 풀이1. 도화지와 그림을 입력받습니다.2. 그림의 개수를 세는 변수와 함수 내에서 그림의 넓이를 저장하는 변수, 가장 큰 넓이를 저장할 변수를 만듭니다.3. dfs 함수를 만드는데 함수 내에서는 도화지 범위 안에서 상하좌우를 그림일 경우만 탐색합니다.4. 탐색하면서 그림의 넓이를 저장합니다.5. 탐색을 마쳤을때..

• format_list_bulleted BAEKJOON/DFS
• · 2024. 11. 27.
• textsms

C++ / 4963 / 섬의 개수 ( 깊이 우선 탐색 )

https://www.acmicpc.net/problem/4963문제 요약정사각형으로 이루어져 있는 섬과 바다 지도가 주어집니다. 섬의 개수를 세는 프로그램을 작성해야합니다.한 정사각형과 가로,  세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형입니다.두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 합니다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없습니다.문제 풀이1. while문으로 입력받는 지도 크기가 0, 0 이 아닐때 계속합니다.2. 지도는 3차원 배열 벡터로 받는데, 지도 개수는 계속 증가 하기 때문에 매 회차 마다 벡터 사이즈를 재정의하여 증가 시켜줍니다.3. 지도 넓이 만큼 벡터 사이즈를 초기화 해주고 지..

• format_list_bulleted BAEKJOON/DFS
• · 2024. 11. 26.
• textsms

C++ / 30702 /국기 색칠하기 ( 깊이 우선 탐색 )

https://www.acmicpc.net/problem/30702문제 요약국기는 n행 m열의 격자판 ( 행열 )으로 구성되어 있습니다. 격자판의 각 칸을 이루는 색은 A부터 Z까지의 영어 알파벳 대문자로 표현합니다. A[ i ][ j ] 를 국기 A의 i행 j열의 색이라고 합니다. 두 국기 A, B가 주어졌을 때, 모든 i, j에대해 A[ i ][ j ]와 B[ i ][ j ]가 같으면 둘은 같은 국기 입니다. 국기 A를 적절히 색칠하여 국기 B와 같게 만들려고 합니다. 국기를 색칠할 때는 다음과 같은 동작을 0회 이상 반복해야 합니다. 국기의 격자판 중 한  칸을 고르고, 이 칸과 같은 구역에 속한 모든 칸을 찾는다. 두 칸이 같은색이면서 상하좌우로 인접해 있을 경우 둘은 같은 구역에 속합니다. 이후..

• format_list_bulleted BAEKJOON/DFS
• · 2024. 11. 25.
• textsms

C++ / 2133 / 타일 채우기 ( 다이나믹 프로그래밍 )

https://www.acmicpc.net/problem/2133문제 요약3 * n 크기의 벽을 2 * 1, 1 *2 크기의 타일로 채우는 경우으 수를 구해야합니다. 아래 그림은 3 * 12 벽을 타일로 채운 예시입니다.  전에 풀었었던 타일 문제와  비슷합니다.https://lgj415415.tistory.com/41 C++ / 11726 / 2 x n 타일링 ( 다이나믹 프로그래밍 )https://www.acmicpc.net/problem/11726문제 요약2 x n 크기의 직사각형을 1 x 2, 2 x 1 타일로 채우는 방법의 수를 구하는 프로그램을 작성해야합니다. 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,lgj415415.tistory.com 문제 풀이1. 벽크기를 입력 받습니..

• format_list_bulleted BAEKJOON/Dynamic Programming
• · 2024. 11. 24.
• textsms

C++ / 12851 / 숨바꼭질 2 ( 너비 우선 탐색 )

https://www.acmicpc.net/problem/12851문제 요약수빈이는 동생과 숨바꼭질을 하고 있습니다. 수빈이는 현재 점 n에 있고, 동생은 점 k에 있습니다. 수빈이는 걷거나 순간이동을 할 수 있습니다. 만약, 수빈이의 위치가 x일 때 걷는다면 1초 후에 x - 1 또는 x + 1로 이동하게 됩니다. 순간이동을 하는 경우에는 1초 후에 2 * x의 위치로 이동하게 됩니다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시가능로 찾는 방법이 몇가지 인지 구하는 프로그램을 작성해야 합니다. 이 문제는 숨바꼭질 1과 이어지는 문제입니다.https://lgj415415.tistory.com/72 C++ / 1697 / 숨바..

• format_list_bulleted BAEKJOON/BFS
• · 2024. 11. 23.
• textsms

C++ / 1697 / 숨바꼭질 ( 너비 우선 탐색 )

https://www.acmicpc.net/problem/1697문제 요약수빈이는 동생과 숨바꼭질을 하고 있습니다. 수빈이는 현재 점 n에 있고, 동생은 점 k에 있습니다.수빈이는 걷거나 순간이동을 할 수 있습니다. 만약, 수빈이의 위치가 x일 때 걷는 다면 1초후에 x - 1 도는 x + 1로 이동하게 됩니다.순간이동을 하는 경우에는 1초 후에 2 * x의 위치로 이동하게 됩니다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성해야합니다.문제 풀이1. 수빈이와 동생의 위치를 입력받습니다.2. bfs 함수를 만듭니다. 매개변수로 탐색을 시작할 노드를 받고 큐에 넣습니다.노드 기준으로 이전 숫자, 다음 숫자, 두배인 숫자로 탐색을 ..

• format_list_bulleted BAEKJOON/BFS
• · 2024. 11. 22.
• textsms