공부 190일차: 백준 16929번 Two Dots 자바 java

16929 Two Dots

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

16929번: Two Dots

 

 

 

---

백준 16929번 문제 Two Dots

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	8024	3686	2335	43.129%

문제

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

점 k개 d₁, d₂, ..., d_k로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다. 
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, d_i와 d_i+1은 인접하다. 또, d_k와 d₁도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

입력

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

출력

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

제한

• 2 ≤ N, M ≤ 50

예제 입력 1

3 4
AAAA
ABCA
AAAA

예제 출력 1

Yes

예제 입력 2

3 4
AAAA
ABCA
AADA

예제 출력 2

No

예제 입력 3

4 4
YYYR
BYBY
BBBY
BBBY

예제 출력 3

Yes

예제 입력 4

7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB

예제 출력 4

Yes

예제 입력 5

2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ

예제 출력 5

No

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

사이클을 완성하려면
1. 4개 이상일 때 처음 시작한 부분으로 돌아오기
1-1. 근데 시작 지점의 옆에서 돌아오는 건 안 됨
1-2. 그렇다고 true를 주면 다시 못돌아옴
==> 방문하지 말고 처음 시작점에 갈 수 있는지만 확인하면 됨

 

 

 

---

정답 인정 코드

---

 

1)

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m, startX, startY;
    static char[][] matrix;
    static boolean[][] visited;
    static Set<Character> s = new HashSet<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static String result = "No";
    
    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());
        matrix = new char[n][m];
        visited = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < m; j++) {
                char ch = str.charAt(j);
                matrix[i][j] = ch;
                s.add(ch);
            }
        }
        Iterator<Character> it = s.iterator();    // set에서 꺼내기 위한 반복자
        while(it.hasNext()) {
            char color = it.next();    // 색깔별로 확인하기 위함
            
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(color == matrix[i][j] && !visited[i][j]) {
                        startX = i;
                        startY = j;
                        DFS(i, j, 1, color);
                    }
                }
            }
        }
        System.out.println(result);
    }
 
    static void DFS(int x, int y, int depth, char color) {
        visited[x][y] = true;    // 방문 처리
        
        for(int i = 0; i < 4; i++) {    // 상하좌우
            int X = x + dx[i];
            int Y = y + dy[i];
            if(X < n && X > -1 && Y < m && Y > -1){    // 범위 안                
                if(depth >= 4 && X == startX && Y == startY) {    // 다음에서 4 이상인 사이클이 완성되면
                    result = "Yes";
                    return;
                }
                if(!visited[X][Y] && matrix[X][Y] == color) {
                    DFS(X, Y, depth+1, color);
                }
            }
        }
        visited[x][y] = false;    // 다른 색깔의 초기화를 위함
    }
}

 

그런데 내 기존 방법과 매우 유사한 이 블로그를 보고

색깔별로 한 시작점에서만 하면 안 된다는 걸 깨달았다 (홀로 떨어진 색깔도 있을 수 있기 때문)

2) set에 색깔 저장하지 않기

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m, startX, startY;
    static char[][] matrix;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static String result = "No";
    
    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());
        matrix = new char[n][m];
        visited = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < m; j++) {
                char ch = str.charAt(j);
                matrix[i][j] = ch;
            }
        }
 
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!visited[i][j]) {
                    startX = i;
                    startY = j;
                    DFS(i, j, 1, matrix[i][j]);
                }
            }
        }
            
        System.out.println(result);
    }
 
    static void DFS(int x, int y, int depth, char color) {
        visited[x][y] = true;    // 방문 처리
        
        for(int i = 0; i < 4; i++) {    // 상하좌우
            int X = x + dx[i];
            int Y = y + dy[i];
            if(X < n && X > -1 && Y < m && Y > -1){    // 범위 안                
                if(depth >= 4 && X == startX && Y == startY) {    // 다음에서 4 이상인 사이클이 완성되면
                    result = "Yes";
                    return;
                }
                if(!visited[X][Y] && matrix[X][Y] == color) {
                    DFS(X, Y, depth+1, color);
                }
            }
        }
        visited[x][y] = false;    // 다른 색깔의 초기화를 위함
    }
}

 

 

 

---