Hey Tech

📝 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 접근법 BFS 알고리즘과 큐(Queue) 자료구조를 활용하여 문제를 해결하였습니다. 문제해결 절차는 다음과 같습니다. 모든 국가를 대상으로 각각 중심국으로 선정하고, 상하좌우 방면에 연합이 가능한 인접국이 있는지 탐색하니다. 만일 연합국이 성립된다면, 해당 인접국을 중심으로 다시 상하좌우 방면의 인접국과 연합국이 성립되는지 여부를 확인합니다. 이 과정은 상하좌우 방면으로..

📝 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 💡 접근법 BFS 알고리즘과 큐(Queue) 자료구조를 활용하여 문제를 해결하였습니다. 빨간 공과 파란 공의 좌표 정보와 보드를 기울인 횟수를 저장하는 큐가 빌 때까지 다음 작업을 반복합니다. 공이 움직일 수 있을 때까지 반복문을 활용하여 상하좌우 방향으로 움직이게 하며, 보드를 기울인 방향으로 공이 모두 움직였다면 큐에 공들의 좌표와 기..

📝 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 💡 접근법 1) 알고리즘 및 자료구조 BFS 알고리즘과 큐(Queue) 자료구조를 활용하여 문제를 해결하였습니다. 상어가 새로운 좌표로 이동하면, 탐색 시작점 역시 해당 새로운 좌표로 이동한 것과 같습니다. 따라서 초기 상어의 위치를 큐에 넣고 탐색할 때마다 꺼내며, 새로운 좌표로 이동할 때마다 큐에 넣는 과정을 반복하면 됩니다. 2) 문제풀이 전략 상어는 가능한 최대한 많은 물고..

📝 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 접근법 1) 문제해결 절차 문제해결 절차는 다음과 같이 크게 3단계입니다. 1️⃣ 벽을 세울 수 있는 3개 지점의 모든 조합 찾기 2️⃣ 앞서 1️⃣에서 정한 지점에 벽을 세우고 바이러스 전파 3️⃣ 가장 넓은 안전지대의 범위 출력 2) 문제해결 방법 BFS 알고리즘을 활용하여 문제를 해결하였습니다. 조합(combination)을 사용한 경우와 하지 않은 경우를 나누어 풀어봤습니다. 각각 나누어 ..

본 포스팅에서는 너비 우선 탐색이라고 불리는 BFS(Breadth-First Search)에 대해 알아봅니다. 📚 목차 1. BFS 알고리즘이란? 2. BFS 알고리즘 동작 과정 3. BFS 파이썬 구현 3.1. 소스코드 설명 3.2. 전체 소스코드 1. BFS 알고리즘이란? BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘입니다. BFS 알고리즘은 언제 사용하면 좋을까요? BFS 알고리즘은 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있는 알고리즘입니다. 그리고 "미로를 빠져나가는 최단 거리(경로)"를 구하는 문제 등에서 효과적으로 활용할 수 있는 알고리즘입니다...

본 포스팅에서는 큐(Queue) 자료구조에 대해 알아봅니다. 📚 목차 1. 큐(Queue) 자료구조란? 2. 큐 동작 예시 3. 큐 구현(Python) 1. 큐(Queue) 자료구조란? 큐 자료구조는 선입선출(先入先出, First In First Out, 줄여서 FIFO) 구조로 흔히 놀이공원 내 놀이기구 대기줄에 비유합니다(그림 1 참고). 즉, 놀이기구 대기줄에 먼저 선 사람(데이터 입력)이 먼저 놀이기구를 타는(데이터 출력/제거) 방식입니다(단, 새치기는 없다고 가정). 큐 자료구조는 아래 2가지 핵심적인 함수로 동작합니다. 데이터 삽입(append) 데이터 삭제(popleft) 큐 자료구조를 사용할 때는 오버플로우(Overflow)와 언더플로우(Underflow)가 발생하지 않도록 유의해야 합니다..