BFS 2

[알고리즘] 시뮬레이션

시뮬레이션의 사전적 정의는 다음과 같다.시뮬레이션 : 실제로 실행하기 어려운 과정을 간단히 행하는 모의실험 코딩테스트에서도 마찬가지로 간단하게 주어지는 조건을 따라 한단계씩 순차적으로 특정 과정을 수행하는 것을 말한다. 주로 캐릭터를 2차원 공간에서 이동하는 문제가 있다고 한다. 구현의 한 종류에 속하기 때문에 특정한 기술보다는 상세한 사고과정이 필요하다. 구현 문제는 머릿속으로 사고하기는 쉽지만 실제 코드로 옮기는 것이 어렵기 때문이다. 예시 문제로는 백준의 2638. 치즈가 있다.https://www.acmicpc.net/problem/2638 적용한 문제 해결방식은 아래와 같다. 1. 치즈가 없어질 때까지 시간은 계속 흘러간다.2. 한시간이 지난 뒤에 남은 치즈를 Flood Fill을 이용해 개수를..

코딩테스트 2024.10.08

[알고리즘] 2차원 배열에서의 Union Find 알고리즘의 적용

2차원에서의 유니온 파인드(Union-Find, 또는 Disjoint Set)는 일반적인 1차원 유니온 파인드의 아이디어를 확장한 것이다. 이를 2차원 배열에서 사용하려면 각 셀을 노드로 간주하고, 인접한 셀들(상하좌우)을 연결하는 방식으로 적용할 수 있다. 이 과정에서 최적화를 위해 그리디 알고리즘을 사용할 수 있는 방법도 있다.1. 2차원 유니온 파인드 구조화2차원 그리드에서 유니온 파인드를 사용하는 대표적인 문제로는 "섬의 개수 찾기", "2차원 퍼즐 해결" 등이 있다. 각 셀을 노드로 보고, 상하좌우로 인접한 셀들을 서로 연결할 수 있는 조건이 충족되면 Union 연산을 적용한다. Union-Find의 핵심은 셀들이 속한 그룹(집합)을 효율적으로 관리하는 것이다. 2차원 좌표의 변환유니온 파인드의..

코딩테스트 2024.10.01