전쟁 - 전투


작성일 : 2017-01-09 07:21:39
조회수 : 532



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


대표적인 깊이 우선 탐색(DFS) 문제입니다.

뭉쳐있는 경우, 즉 '동서남북' 으로 자신과 같은 옷의 병사가 뭉쳐 있을 경우를 찾아야 합니다.


탐색을 하기 위해 재귀 함수를 작성합니다.

이 때, 한 번 방문했던 지점을 다시 방문하게 될 경우 재귀가 무한정 들어가게 되어 stack overflow가 발생합니다.


그러므로 방문을 체크하는 boolean 배열을 선언한 후, 방문한 지점을 체크하도록 하면 됩니다.

원리만 이해한다면 풀기는 쉬운 문제입니다.

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s[101];
bool visited[101][101];
int w,h,cnt[26], ans[26];
void dfs(int x, int y, char c)
{
    visited[x][y] = true;
    cnt[c - 'A']++;
    if (x > 0 && !visited[x - 1][y] && s[x - 1][y] == c) dfs(x - 1, y, c);
    if (y > 0 && !visited[x][y - 1] && s[x][y - 1] == c) dfs(x, y - 1, c);
    if (x + 1 < h && !visited[x + 1][y] && s[x + 1][y] == c) dfs(x + 1, y, c);
    if (y + 1 < w && !visited[x][y + 1] && s[x][y + 1] == c) dfs(x, y + 1, c);
}
int main()
{
    ios::sync_with_stdio(false);

    cin >> w >> h;
    for (int i = 0; i < h; i++) cin >> s[i];
    for(int i=0; i<h; i++)
        for (int j = 0; j < w; j++)
        {
            if (!visited[i][j])
            {
                int q = s[i][j] - 'A';
                dfs(i, j, s[i][j]);
                ans[q] += cnt[q]* cnt[q];
                cnt[q] = 0;
            }
        }
    cout << ans[22] << " " << ans[1];
}

전쟁 - 전투 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글