프로그래밍/알고리즘
BOJ 6189 · Munching
알고리즘 분류 : BFS 전형적인 미로 탈출 문제이다. BFS를 통해 최단 이동 거리를 구하면 된다. 'B'부터 출발해서 'C'에 도착하면 된다.장애물('*')은 지날 수 없다.인접 4방향으로 BFS 탐색을 진행하면 된다. C++ 소스코드 #include #include using namespace std; struct grid { int x, y; }; int r, c, sx, sy; char a[101][101]; int dist[100][100]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void bfs() { queue q; q.push({sx, sy}); dist[sx][sy] = 0; while (!q.empty()) { int x = q..
BOJ 6186 · Best Grass
알고리즘 분류 : DFS, BFS 풀덤불의 개수를 구하는 문제다. 기본적인 플러드 필 알고리즘을 구현하면 된다. R*C 사이즈의 맵을 탐색하면서 서로 연결된 풀(#)을 찾는다. 연결된 그룹을 하나의 덤불로 카운트한다.모든 영역의 탐색이 끝날 때까지 DFS를 진행한다. C++ 소스코드 #include int r, c, ans; char a[101][101]; bool check[100][100]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void dfs(int x, int y) { check[x][y] = true; for (int i=0; i
BOJ 11567 · 선진이의 겨울 왕국
알고리즘 분류 : BFS 빙판길 탈출 가능 여부를 구현하는 문제다. 빙판길은 손상되지 않은 상태(.)와 손상된 상태(X)가 있다. 초기 위치는 항상 손상된 상태로 주어지며, 탈출구는 손상시켜서 빙판을 없애야 한다. BFS를 통해 맵을 탐색하고, 탈출구 부분은 왔다 갔다 하면서 무너뜨려서 탈출해야 한다. 출발 좌표를 (SX, SY), 도착 좌표를 (EX, EY)라 하자.(SX, SY)부터 BFS 탐색을 진행하면서, 다음 이동 좌표가 (EX, EY)인지 확인해야 한다. 1. 만약 (EX, EY)라면, 손상되지 않은 상태(.)인지 손상된 상태(X)인지 확인해야 한다.손상되지 않은 상태라면, 한 번 밟은 것이므로 손상된 상태로 바꾼다. 도착 좌표를 큐에 집어넣는다.손상된 상태라면, 탈출이 가능한 것이므로, "Y..
BOJ 5980 · Corn Maze
알고리즘 분류 : BFS BFS를 이용하여 미로 탈출을 하는 것을 구현해야 한다. 일반적인 탈출 BFS와 같으나, 맵에서 순간 이동이 가능하다. 순간 이동하는 부분을 잘 처리하는 것이 관건이다. 출발점(@)부터 출구(=)까지 도달하는 최단 거리를 구해야 한다.순간 이동(A~Z)는 쌍으로 이루어져 있으며, 이동 비용은 없다.알파벳 총개수(26) 만큼 리스트를 만들어 둔다. 입력받을 때, 대문자 알파벳인 경우 해당 좌표를 리스트에 저장한다.BFS를 통해 이동하다가 순간 이동 입구에 도착하면, 리스트에 있는 좌표를 꺼내서 반대편 입구로 넘어간다. 넘어간 곳의 좌표를 큐에 집어넣는다.풀(.)이면 일반적인 이동이 가능하다. 방문 체크를 하고, 이동 좌표를 큐에 집어넣는다.위 과정을 출구에 도착할 때까지 반복한다...
BOJ 1926 · 그림
알고리즘 분류 : DFS, BFS 그림의 개수와 최대 넓이를 구하는 문제다. 플러드 필을 구현하면 된다. 아직 확인하지 않은 그림 조각(1)부터 출발하여 인접하여 연결된 모든 그림을 DFS나 BFS로 탐색한다.연결된 그림 조각의 개수는 그림의 넓이를 의미한다. 이중 가장 큰 값이 그림의 최대 넓이이다.그림의 넓이를 확인했으면, 그림의 개수를 카운트한다. C++ 소스코드 #include int n, m, cnt, area; int a[500][500]; bool check[500][500]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int dfs(int x, int y) { int ret = 1; check[x][y] = true; for (int i..
BOJ 1303 · 전쟁 - 전투
알고리즘 분류 : DFS, BFS 각 팀의 전투력 합을 구하는 문제다. 플러드 필을 하면 된다. 시작 알파벳을 기준으로 DFS나 BFS를 통해 인접하면서 같은 알파벳을 찾는다.모인 팀의 인원을 제곱한 후, 각 팀 전투력에 더한다.W팀, B팀의 전투력을 각각 출력한다. C++ 소스코드 #include int n, m, w, b; char a[101][101]; bool check[100][100]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int dfs(int x, int y, char c) { int ret = 1; check[x][y] = true; for (int i=0; i
BOJ 1743 · 음식물 피하기
알고리즘 분류 : DFS, BFS 음식물 덩어리의 최대 크기를 구하는 문제다. 간단한 플러드 필 문제이다. N*M 사이즈의 맵을 만들고 0으로 모두 채운다.입력으로 주어지는 음식물의 위치를 맵에 1로 채운다.음식물(1)을 기준으로 DFS 또는 BFS 탐색을 하여 연결된 음식물을 찾는다.가장 큰 음식물을 정답으로 낸다. C++ 소스코드 #include int n, m, k, ans; int a[100][100]; bool check[100][100]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int dfs(int x, int y) { int ret = 1; check[x][y] = true; for (int i=0; i
BOJ 16946 · 벽 부수고 이동하기 4
알고리즘 분류 : DFS, BFS 벽 부수고 이동하기 네 번째 문제다. 이번 문제는 이전 문제들과 완전히 다르다. 플러드 필 알고리즘을 구현하는 문제이다. 기본 아이디어기본적으로, 각 벽(1)부터 DFS를 시작하여 빈칸(0)을 향해 뻗어나가는 방식을 생각할 수 있다.구현은 간단하지만, 최대 1000*1000 사이즈가 입력으로 주어지므로 시간 초과가 난다. 개선 아이디어배열 A를 DFS를 통해 완전 탐색한다.1. 빈칸(0)부터 시작하여 인접한 빈칸의 개수를 모두 세면서 리스트 V에 기록해둔다.2. 빈칸의 개수를 셀 때, 배열 B에 각 빈칸마다 넘버링을 해둔다.1~2 과정을 맵 전체에 한다.배열 A에서 각 벽(1)마다 인접한 4칸을 확인하고, 배열 B를 통해 저장해둔 넘버링이 있는지 확인한다.Set 자료구조..