[백준] 14271 : 그리드 게임 (Python)

출처 : https://www.acmicpc.net/problem/14271  아이디어해당 문제는 상하좌우 근접 칸을 탐색해야 하는 문제이므로, 그래프 탐색 유형이다. 먼저, 그리드의 칸이 변하는 규칙을 바탕으로, 요구사항이 어떤 의미를 가지는지 파악해보자.요구사항 파악'크기가 무한대이고, 단위 정사각형으로 나누어져 있는 그리드'해당 사진을 통해 알 수 있듯이, 2 by 2 행렬이 4 by 4로 점점 확장되는 모습을 확인해볼 수 있다. 만약, 확장되는 형식으로 그래프를 탐색해야 한다면 완전 탐색이 될 수 밖에 없으므로 O(n**2) 시간 복잡도를 가지게 된다.완전 탐색을 피하기 위해서는 '행렬의 크기가 진짜 무한대인가'를 따져봐야 한다. 커지는 규칙이 존재하는데 그것이 K이다. 얼마나 커지는지는 후술하도..

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

[백준] 28107 : 회전초밥 (Python)

출처 : https://www.acmicpc.net/problem/28107   아이디어해당 문제는 결론부터 말하자면, 우선순위 큐(heap) 유형으로 구분할 수 있다. 그러한 이유를 자세히 살펴보자. 먼저, 핵심 요구사항들을 파악하는 것부터 시작해보자.'1번 손님부터 순서대로 초밥을 먹는다.'여러 명이 같은 초밥을 시켰을 때, 가장 번호가 낮은 손님이 우선권을 갖는다.'각 손님은 자신의 주문 목록에 적힌 순서와 상관없이, 초밥이 존재하면 반드시 먹는다.'주문 목록에 적힌 순서대로 먹는 것이 아닌, 초밥을 기입했냐 안했냐인 존재 여부만을 따진다.'각 종류의 초밥을 한번만 먹는다.'한 손님이 같은 초밥을 여러 개 시킬 일은 존재하지 않는다. (중복 x) 우선권이라는 인사이트를 파악했다면, 사실 우선순위 큐..

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

[백준] 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.

[백준] 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.