백준

백준 16724 피리 부는 사나이

콩순이냉장고 2022. 3. 22. 19:41

문제 URL : https://www.acmicpc.net/problem/16724

 

16724번: 피리 부는 사나이

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주

www.acmicpc.net

 

문제 접근법 : 

 

문제가 설명이 뭔가 저한테는 이상하더라구여 무슨말인지 이해를 못해서

싸이클의 갯수를 구한다는 말 이라는걸 알고 풀수있었습니다.

 

싸이클의수를 구하기위해 여러가지 방법이 있지만

저는 dfs를 사용했습니다.

다른 해설에 union find를 사용했는데 제실력이 부족한 관계로 아직은 그렇게 해결은 아직 무리인가봅니다.

 

 

 

소스코드 : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
char board[1000][1000];
int dy[4= { -1,0,1,0 };
int dx[4= { 0,1,0,-1 };
int n, m;
char dir[255];
int check[1000][1000];
int res = 0;
bool isrange(int y, int x) {
    return 0 <= y && y < n && 0 <= x && x < m;
}
void dfs(int y,int x) {
    check[y][x] = 1;
    int ny = y + dy[dir[board[y][x]]];
    int nx = x + dx[dir[board[y][x]]];
    if (check[ny][nx]== 1)res++;
    if (check[ny][nx] == 0)dfs(ny, nx);
    check[y][x] = 2;
}
void input() {
    cin >> n >> m;
    dir['R'= 1;
    dir['D'= 2;
    dir['L'= 3;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
    
}
 
void solve() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (check[i][j] == 0) {
                dfs(i, j);
            }
        }
    }
    cout << res << "\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    input();
    solve();
}
cs

 

 

 

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.