[백준] 6191 : Cows on Skates (Python)

출처 : https://www.acmicpc.net/problem/6191   아이디어장애물로 구분되는 2차원 행렬이라는 점과 인접한 상하좌우 칸으로 점점 확장해나가는 요구사항을 지니고 있으므로, 그래프 탐색 유형의 문제임을 알 수 있다. DFS vs BFS'적어도 1가지 방법이 존재하고, 해당 경로를 출력해라.'해당 요구사항을 통해, 경로는 1가지만 존재하며 지나온 좌표들을 모두 출력하라는 인사이트를 알 수 있다. 최소/최대의 경로길이가 아닌, 1가지의 경로 출력이므로 DFS/BFS를 모두 사용 가능하다. 필자는 BFS를 선택하였다. Queue 원소 형식다음의 시각화 그래프를 통해 알아보자.(1,2)로 갈때는 부모의 경로 배열에 더해지고, 마찬가지로 (1,3)으로 갈때도 부모 배열에서 더해진다. 즉, ..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 13.

[백준] 1463 : 1로 만들기 (Python)

출처 : https://www.acmicpc.net/problem/1463  아이디어해당 문제는 3가지 연산이 트리의 간선들로 연결되고 루트 노드가 X로 고정되있으므로, 특수 그래프 트리의 탐색 유형임을 알 수 있다. 이를 바탕으로, 다음 3가지의 알고리즘 탐색 기법을 설계해보았다.BFS + MemoDP - Top Down (DFS+Memo)DP - Bottom-Up (For Loop)일반적으로 시간 효율성은 DP -> BFS이므로, DP의 접근 방식을 선택하였고 이에 대해 자세히 살펴보자. (물론, 해당 문제의 경우는 BFS로도 잘 풀릴 수 있지만, 일반적인 문제들의 경우는 두 기법 모두 접근 방식이 다를 수 있다.) DP가 가능한 이유해당 문제를 시각화하면 다음 사진과 같다.각 노드에 3가지의 서브트..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 11.

[백준] 2210 : 숫자판 점프 (Python)

출처 : https://www.acmicpc.net/problem/2210   아이디어이번 문제는 상하좌우로 탐색을 진행해야 하는 그래프 탐색 유형이다. 요구사항 분석을 통해 DFS와 BFS의 탐색 과정을 어떻게 설정해야하는지 확인해보자. '한 번 거쳤던 칸을 다시 거쳐도 된다.'일반적으로는 해당 요구사항은 백트래킹으로 해석할 수 있다. 그러나, 이번 문제에서는 백트래킹이 아니라, '단순히 이전에 방문했던 칸을 다시 탐색해도 된다.'라는 의미를 가진다. 즉, 방문처리를 따로 하지 않고, 온전히 상하좌우 방향을 모두 탐색하는 설계를 세울 수 있다는 뜻이다. 여기서 우리는 다음과 같은 의문점이 생긴다.'방문처리를 하지 않으면, 어떻게 탐색 종료 조건을 넣어야 하는가?'이러한 의문점에 대한 해답인 인사이트는 ..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 10.

[백준] 6067 : Guarding the Farm (Python)

출처 : https://www.acmicpc.net/problem/6067 아이디어해당 문제는 상하좌우 칸을 체크하며, 산봉우리에 포함되는 지역인지 확인해야하기 때문에 그래프 탐색 문제 유형으로 해석할 수 있다. 요구사항을 바탕으로, 어떻게 산봉우리 개수를 출력할지 생각해보자. '인접하다'의 정의는 X좌표 차이와 Y좌표 차이가 모두 1이하인 경우상하좌우뿐만 아니라, 대각선도 인접하다는 사실을 알 수 있다. 즉, 인접 칸(노드)들을 탐색하게 되는 간선이 8개가 존재한다. 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야 한다.산봉우리의 고도는 가장 커야 한다는 의미이다. 이를 통해, 산봉우리는 지역(덩어리)로 구분이 되고, 이에 따른 지역(덩어리) 개수를 출력해야하므로, BFS 탐색을 몇번 하는가를..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 9.

[백준] 9184 : 신나는 함수 실행 (Python)

출처 : https://www.acmicpc.net/problem/9184 문제재귀 호출만 생각하면 신이 난다! 아닌가요?다음과 같은 재귀함수 w(a, b, c)가 있다.if a 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.입력입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 8.

[백준] 15900 : 나무탈출 (Python)

출처 : https://www.acmicpc.net/problem/15900 문제평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다.'나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다.이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임말이 하나..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 7.