[백준] Two Dots 16929번

사이트

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

16929번: Two Dots

 

문제

 

풀이 

문제는 간단했다. 똑같은 문자를 기준으로 1개의 순환 구조만 있으면 Yes 아니면 No만 뜨게 하는 문제이다. 

 

필자는 당연히 dfs로 생각해서 풀었다. 맨날 bfs로만 풀어서 익숙치 않았지만 이 문제는 dfs로 해결을 해야될거 같아서 풀어봤다. 

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());

graph = new char[n][m];
visit = new boolean[n][m];

for (int i = 0; i < n; i++) {
    String row = br.readLine();
    for (int j = 0; j < m; j++) {
        graph[i][j] = row.charAt(j);
    }
}

문자를 입력받아야 되므로 위와 같이 받아주었다. 

 

outerLoop:
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        visit = new boolean[n][m];
        visit[i][j] = true;
        startX = i;
        startY = j;
        alphabet = graph[i][j];
        dfs(0, i, j);
        if (message.equals("Yes")) {
            break outerLoop;
        }

    }
}

 

dfs로 풀기 위해서 위 for문에 첫 시작점 좌표 위치인 startX와 startY를 배정해준다.

배정해준 이유는 나중에 dfs()함수에서 순환을 다 돌았을때 해당 위치가 처음 위치랑 맞는지 확인 시켜주기 위함이다. 

 

그리고 해당 위치 문자를 alphabet 변수에 넣는다. 참고로 alphabet은 static변수이다. 

입력을 위 사진에 첫번째로 했을때

첫 시작이므로 startX, startY는 각각 0이고 alphabet은 현재 A이다.  

그리고 dfs 실행!! 

 

message가 static 변수로 현재 No로 초기화 되어있는데 dfs()함수에서 Yes라고 뜨는 것과 동시에 0,0인 dfs가 종료되면 바로 for문을 나가게 된다.  

private static void dfs(int depth, int staticX, int staticY) {
    for (int i = 0; i < 4; i++) {
        int nextX = dx[i] + staticX;
        int nextY = dy[i] + staticY;
        if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && alphabet == graph[nextX][nextY]) {
            if (!visit[nextX][nextY]) {
                visit[nextX][nextY] = true;
                dfs(depth + 1, nextX, nextY);
            } else {
                if (depth >= 3 && nextX == startX && nextY == startY) {
                    message = "Yes";

                }
            }
        }
    }
}

dfs()함수이다. 차근 차근 보자

위 for문에서 dfs(0,i,j) 가 들어온다. 즉 i랑 j는 현재 각각0이다. 

dfs함수에서는 staticX staticY로 명칭을 했다.

 

nextX랑 nextY변수에 dx dy 배열이랑 staticX Y를 합했다. 

static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};

 

참고로 dx dy 배열은 위와 같은데 저렇게 해준이유가 그래프 안에서 상하좌우로 한칸씩 이동하기 위해서 이다. 

 

if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && alphabet == graph[nextX][nextY]) {
    if (!visit[nextX][nextY]) {
        visit[nextX][nextY] = true;
        dfs(depth + 1, nextX, nextY);
    } else {
        if (depth >= 3 && nextX == startX && nextY == startY) {
            message = "Yes";

        }
    }
}

그럼 처음 if문에 그래프의 범위가 맞는지 확인함과 동시에 alphabet현재 A인데 next한 알파벳이 A랑 맞으면 들어온다. 

 

만약 방문하지 않는 위치이면 if문에 걸려서 next 위치를 true로 바꿔주고 다음 dfs 문을 실행하게 된다. 

 

만약 방문한 위치이면 else로 이동하는데 이때 깊이가 3이상이고 next한 위치가 첫 시작인 start랑 맞으면 

message가 Yes로 바뀐다. 

 

만약 방문한 위치인데 if문에 맞이 않으면 다음 next위치로 이동하면서 실행된다. 

 

참고로 dfs 3이상을 넣은 이유는 문제 무조건 4개 지나가야 된다고 해서 넣은 것이다. 

만약 저 조건을 안 넣을시 AA도 루프로 맞게 처리하게 되기 때문이다. 

 

 

 

 

전체 코드

package graph;

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

public class Graph16929 {
    static int n;

    static int m;

    static char[][] graph;

    static boolean[][] visit;

    static int startX;
    static int startY;

    static char alphabet;

    static String message = "No";

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

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

        graph = new char[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String row = br.readLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = row.charAt(j);
            }
        }
        outerLoop:
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visit = new boolean[n][m];
                visit[i][j] = true;
                startX = i;
                startY = j;
                alphabet = graph[i][j];
                dfs(0, i, j);
                if (message.equals("Yes")) {
                    break outerLoop;
                }

            }
        }

        System.out.println(message);

    }

    private static void dfs(int depth, int staticX, int staticY) {
        for (int i = 0; i < 4; i++) {
            int nextX = dx[i] + staticX;
            int nextY = dy[i] + staticY;
            if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && alphabet == graph[nextX][nextY]) {
                if (!visit[nextX][nextY]) {
                    visit[nextX][nextY] = true;
                    dfs(depth + 1, nextX, nextY);
                } else {
                    if (depth >= 3 && nextX == startX && nextY == startY) {
                        message = "Yes";

                    }
                }
            }
        }
    }
}

 

 

결과

 

 

느낀점

뭔가 쉬웠는데 의외로 어려웠다. 역시 골드 문제.... 
depth 3 이상 조건을 넣는게 핵심이였다. 이거 안넣어서 계속 틀렸다... 추가로 조건문 구성도 잘 넣어야 했다.