전체 글
BOJ 11370 · Spawn of Ungoliant
알고리즘 분류 : DFS 거미가 영역을 확장하는 것을 구현하면 된다. 전형적인 플러드 필 문제이다. 거미의 위치('S')부터 시작해서 DFS로 뻗어나간다.나무('T')에만 뻗어나갈 수 있으며, 거쳐간 나무는 'S'로 바꾼다. C++ 소스코드 #include int h, w; char a[101][101]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int dfs(int x, int y) { for (int i=0; i
BOJ 11123 · 양 한마리... 양 두마리...
알고리즘 분류 : DFS 양 무리를 세는 문제이다. 전형적인 플러드 필 알고리즘이다. H*W 사이즈의 맵을 DFS로 탐색한다.양(#)부터 시작해서, 연결된 양을 찾는다.맵을 모두 탐색할 때까지 진행하여, 양 무리를 카운트한다. C++ 소스코드 #include #include int h, w; 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) { check[x][y] = true; for (int i=0; i
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