반응형

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

 

16929번: Two Dots

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 게임판을 arr 배열에 입력받고, 최종 방문 여부를 저장할 visited2 배열과, dfs를 돌면서 방문을 기록할 visited 배열을 만듭니다.

 

2. 모든 좌표를 돌면서 visited2 배열의 값이 0일 때 dfs를 돌면서 방문한 곳에 한번 더 방문할 때 점의 개수가 4개 이상일 경우 ans의 값을 true로 바꿔줍니다.

 

3. ans가 true이면 Yes를 출력하고, 그렇지 않다면 No를 출력합니다.

 

[ 소스코드 ]

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
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
 
using namespace std;
 
int N, M;
char arr[51][51];
int visited[51][51];
int visited2[51][51];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
bool ans = false;
 
void dfs(int y, int x, int cnt)
{
    if (ans == true) return;
    visited2[y][x] = 1;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
 
        if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
            if (arr[yy][xx] == arr[y][x]) {
                if (visited[yy][xx] != 0) {
                    if (cnt - visited[yy][xx] + 1 >= 4) {
                        ans = true;
                        return;
                    }
                }
                else {
                    visited[yy][xx] = cnt + 1;
                    dfs(yy, xx, cnt + 1);
                    visited[yy][xx] = 0;
                }
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited2[i][j] == 0) {
                visited[i][j] = 1;
                dfs(i, j, 1);
                visited[i][j] = 0;
            }
        }
    }
 
    if (ans) cout << "Yes";
    else cout << "No";
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16934번 - 게임 닉네임 (C++)  (0) 2023.07.25
[ 백준 ] 7432번 - 디스크 트리 (C++)  (0) 2023.07.24
[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20

+ Recent posts

티스토리툴바