DATA101

📝 문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 💡 접근법 DFS 알고리즘을 활용하여 문제를 해결하였습니다. DFS를 통해 특정 좌표에 상하좌우 방면으로 3개의 블록을 이어 붙이면 'ㅏ', 'ㅓ', 'ㅗ', 'ㅜ' 모양을 제외한 모든 테트로미노를 만들 수 있습니다. 'ㅏ', 'ㅓ', 'ㅗ', 'ㅜ' 모양의 테트로미노는 2번째 블록까지 붙였을 때 새로운 블록에서 이어붙일 다음 블록을 탐색하지 않고 다시 기존 블록 위치에서 탐색하도록 로직..

본 포스팅에서는 깊이 우선 탐색 DFS(Depth-First Search) 알고리즘에 대해 알아봅니다. 📚 목차 1. DFS 알고리즘이란? 2. DFS 알고리즘 동작 과정 3. DFS 파이썬 구현 1. DFS 알고리즘이란? DFS(Depth-First Search)는 그래프 전체를 탐색하는 방법(i.e., 완전 탐색) 중 하나로, '깊이'를 우선적으로 탐색하는 알고리즘입니다. DFS는 한 노드를 시작으로 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색합니다. 예를 들어, DFS 알고리즘은 미로 탐색 시 한 방향으로 모든 노드를 방문하다가 더 이상 다른 노드를 방문할 수 없는 노드에 이르렀을 때, 다시 가장 가까운 갈래길로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어가는 방법입니다...