반응형
11-14 12:35
Today
Total
«   2024/11   »
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
관리 메뉴

개발하는 고라니

[백준] 16929번 : Two Dots 본문

Programming/백준

[백준] 16929번 : Two Dots

조용한고라니 2021. 5. 1. 19:45
반응형
 

16929번: Two Dots

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

www.acmicpc.net


[DFS]

DFS를 이용해 A ~ Z로 이루어진 격자에서 사이클이 존재하는지 여부만 판단하면 된다.

 

사이클을 확인하는 알고리즘은 다음과 같이 작성했다.

    static boolean visit = new boolean[51][51];
    static boolean cycle;
    
    /*
    현재 방문하고 있는 정점이 이미 방문되었고, cnt가 4이상이면 cycle을 찾았다고 판단
    */
    
    static void DFS(int y, int x, int bY, int bX, int cnt){

        //현재 정점이 이미 방문한 곳 & 4개 이상을 거쳤는지?
        if(visit[y][x] && cnt >= 4){
            cycle = true;
            return;
        }

        visit[y][x] = true;
        char cur = map[y][x];

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            //범위를 넘지않고, 현재 정점의 알파벳과 동일한지? 바로 다음 정점이 이전 정점과 다른지?
            if(ny < 1 || nx < 1 || ny > n || nx > m || map[ny][nx] != cur) continue;
            if(ny == bY && nx == bX) continue;

            DFS(ny, nx, y, x, cnt + 1);
        }
    }

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int n, m;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static char[][] map = new char[51][51];
    static boolean[][] visit = new boolean[51][51];
    static boolean cycle;

    static void DFS(int y, int x, int bY, int bX, int cnt){

        if(visit[y][x] && cnt >= 4){
            //System.out.println("(" + y+", " + x +") 에서 사이클 발생");
            cycle = true;
            return;
        }

        visit[y][x] = true;
        char cur = map[y][x];

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            if(ny < 1 || nx < 1 || ny > n || nx > m || map[ny][nx] != cur) continue;
            if(ny == bY && nx == bX) continue;

            DFS(ny, nx, y, x, cnt + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=m; j++)
                map[i][j] = str[j-1];
        }

        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++){
                if(!visit[i][j])
                    DFS(i, j, 0, 0, 1);
            }
        System.out.println(cycle? "Yes":"No");
    }
}
반응형

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

[백준] 14950번 : 정복자  (0) 2021.05.02
[백준] 2562번 : 최댓값  (0) 2021.05.01
[백준] 1938번 : 통나무 옮기기  (0) 2021.04.30
[백준] 11021번 : A + B - 7  (0) 2021.04.28
[백준] 16932번 : 모양 만들기  (0) 2021.04.15
Comments