[백준-16724] 피리 부는 사나이

구현 + DFS 문제였다.

네트워크 개수를 세는 듯한 문제인데 입력받은 U, D, L, R 에 따라 쭉~ 이어주는 동시에 다음 값이 현재 있는 값으로 들어올수도 있는지 확인하는 로직을 구현하면 간단한 문제였다. 다시 로직을 정리하면 다음과 같다.

• 지도 (0,0) 부터 check 되어있지 않으면 dfs 로 해당 지점으로부터 연결되어있는 모든 지도지점을 check
• SAFE ZONE 개수 한개 추가
• 그 후 check 안되어있는 지점으로부터 dfs 처리해서 똑같이 네트워크 check
• SAFE ZONE 한개 추가

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
typedef pair<int, string> pii;
char arr[1001][1001];
int check[1001][1001];
int dx[] = { -1,0,1,0 }; // 위, 왼쪽, 아래, 오른쪽
int dy[] = { 0,-1,0,1 };
int n, m;
char dz[] = { 'D', 'R', 'U','L' };

bool dfs_check(int a, int b, int i) {
    return (a<1 || a > n || b < 1 || b > m) || dz[i] != arr[a][b] || check[a][b] == 1;
}
void dfs(int x, int y) {
    switch (arr[x][y]) {
    case 'D':
        if (x + 1 <= n && check[x + 1][y] == 0) 
            check[x + 1][y] = 1, dfs(x + 1, y);
        for (int i = 0; i < 4; i++) {
            if (i == 2) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1, dfs(cx, cy);
        }
        break;
    case 'L':
        if (y - 1 >= 1 && check[x][y-1] == 0) 
            check[x][y - 1] = 1, dfs(x, y - 1);
        for (int i = 0; i < 4; i++) {
            if (i == 1) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1,  dfs(cx, cy);
        }
        break;
    case 'R':
        if (y + 1 <= m && check[x][y + 1] == 0) 
            check[x][y + 1] = 1, dfs(x, y + 1);
        for (int i = 0; i < 4; i++) {
            if (i == 3) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1, dfs(cx, cy);
        }
        break;
    case 'U':
        if (x - 1 >= 1 && check[x - 1][y] == 0) 
            check[x - 1][y] = 1, dfs(x - 1, y);
        for (int i = 0; i < 4; i++) {
            if (i == 0) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1, dfs(cx, cy);
        }
        break;
    }
    return;
}
int main() {
    scanf("%d %d", &n, &m);

    string input;
    for (int i = 1; i <= n; i++) {
        cin >> input;
        for (int j = 1; j <= m; j++) {
            arr[i][j] = input.at(j-1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (check[i][j] == 1) continue;
            check[i][j] = 1;
            dfs(i, j);
            res += 1;
        }
    }

    printf("%d", res);
    return 0;
}

 

 

https://www.acmicpc.net/problem/16724

16724번: 피리 부는 사나이