[BOJ] 백준 16929 Two dots - Python/Java

문제

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

16929번: Two Dots

 

해설

이 문제에서 정의하는 싸이클을 판단하는 기준은 여러가지가 있는 것 같습니다.

 

저같은 경우에는 [1] '시작 노드와 연결된 간선(최대 4개)에 대해 동일한 간선을 이용하지 않고 다시 시작 노드로 돌아올 수 있다면, 싸이클이 형성된다' 라고 생각했습니다.

 

그런데 다른 분들의 풀이를 보니 [2] '시작 노드에 대해서는 방문 체크를 하지 않은 채 DFS 탐색을 하다가, 그 경로의 길이가 3 이상이 되면서 다음 노드가 시작 노드가 될 수 있다면 싸이클이 형성된다'라고 풀이한 것 같습니다.

 

두 풀이 모두 좋은 풀이라고 생각합니다. 다만, 저의 풀이 같은 경우에는 간선에 대한 방문 처리를 해야한다는 점에서 두번째 방법보다는 조금 복잡해지는 부분이 있긴 합니다.

 

풀이는 아래와 같으며, 일반적인 DFS 구현에다가 Edge에 대한 방문 작업을 조금씩 추가한 것입니다.

 

시작 노드에서 출발 할 때만 그 방향에 대한 간선을 방문 체크해주었고, 이후에 시작 노드로 들어오는 간선이 있다면 그 간선을 findEdgeDir(inDir) 함수를 통해 시작 노드에서 나가는 간선인 방향으로 해석하도록 했습니다.

 

풀이 - 파이썬

import sys
input = sys.stdin.readline

def findEdgeDir(inDir): # 들어오는 간선 방향을 나가는 방향 기준으로 변환
    outDir = -1
    if inDir == 0:
        outDir = 1
    elif inDir == 1:
        outDir = 0
    elif inDir == 2:
        outDir = 3
    else:
        outDir = 2
    return outDir
    
# 시작 노드와 연결된 간선을 기준으로 중복 방문 없이 다시 올 수 있는가?
def checkCycle(x, y, startX, startY, visitedNode, visitedEdge):
    visitedNode[x][y] = True
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m: # 범위 체크
            if dots[nx][ny] != dots[x][y]: continue # 같은 모양 체크
            
            if nx == startX and ny == startY: # 시작 노드로 돌아오는 경우
                edgeDir = findEdgeDir(i)
                if not visitedEdge[edgeDir]:
                    return True
            else: # 일반적인 경우 - 다른 노드로 이동하는 경우
                if not visitedNode[nx][ny]:
                    visitedNode[nx][ny] = True
                    if x == startX and y == startY: # 시작 노드에서 나갈 때만 간선에 방문 체크
                        visitedEdge[i] = True
                    if checkCycle(nx, ny, startX, startY, visitedNode, visitedEdge):
                        return True
    return False
                    

n, m = map(int, input().split())
dots = [list(input().rstrip()) for _ in range(n)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
isCycle = False
for i in range(n):
    for j in range(m):
        visitedNode = [[False] * m for _ in range(n)] # 각 노드의 방문 여부
        visitedEdge = [False] * 4 # 시작 노드에서 가질 수 있는 간선 네 개의 방문 여부
        if checkCycle(i, j, i, j, visitedNode, visitedEdge):
            isCycle = True
print("Yes") if isCycle else print("No")

풀이 - 자바

package PS;

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

public class B_16929_TwoDots {
    static int n, m;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static char[][] dots;
    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());
        dots = new char[n][m];
        for(int i = 0; i < n; i++){
            char[] line = br.readLine().toCharArray();
            for(int j = 0; j < m; j++){
                dots[i][j] = line[j];
            }
        }
        boolean isCycle = false; // 싸이클 존재 여부
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                boolean[][] visitedNode = new boolean[n][m];
                boolean[] visitedEdge = new boolean[4];
                if(checkCycle(i, j, i, j, visitedNode, visitedEdge))
                    isCycle = true;
            }
        }
        if(isCycle) System.out.println("Yes");
        else System.out.println("No");
    }

    static boolean checkCycle(int x, int y, int sx, int sy, boolean[][] visitedNode, boolean[] visitedEdge){
        visitedNode[x][y] = true;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(0 <= nx && nx < n && 0 <= ny && ny < m){
                if(dots[nx][ny] != dots[x][y]) continue; // 같은 모양인지 체크

                if(nx == sx && ny == sy){ // 시작 노드로 돌아오는 경우
                    int edgeDir = findEdgeDir(i);
                    if(!visitedEdge[edgeDir]) return true;
                }
                else{ // 일반적인 경우 - 다른 노드로 이동할 때
                    if(!visitedNode[nx][ny]){
                        visitedNode[nx][ny] = true;
                        if(x == sx && y == sy)
                            visitedEdge[i] = true;
                        if(checkCycle(nx, ny, sx, sy, visitedNode, visitedEdge))
                            return true;
                    }
                }
            }
        }
        return false;
    }
    static int findEdgeDir(int inDir){
        switch (inDir){
            case 0:
                return 1;
            case 1:
                return 0;
            case 2:
                return 3;
            case 3:
                return 2;
        }
        return -1;
    }
}