Two Dots

문제 복기

문제

예시

문제 설명

입,출력 예시

위의 문제 설명에서처럼 주어진 조건은 다음과 같다.

1. 모든 k개 점은 서로 다르다.

2. k는 4보다 크거나 같다. =>이동한 칸의 갯수를 세서 4이상이면 된다.

3. 모든 점의 색은 같다. =>어떤 시작점에서 컬러를 기억해서 다음 재귀함수를 호출할 때 인자로 전달하여 컬러 갯수가 같도록 해야한다!

4. 모든 1<i<=k-1에 대해 di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다. "인접" : 상/하/좌/우 방향으로 붙어있다!

알고리즘 생각

문제에서 주어진 조건들을 하나씩 구현해보고, 발전시켜나간다.

• k는 4보다 크거나 같다. =>이동한 칸의 갯수를 세서 4이상이면 된다.

• 모든 점의 색은 같다. =>어떤 시작점에서 컬러를 기억해서 다음 재귀함수를 호출할 때 인자로 전달하여 컬러 갯수가 같도록 해야한다!

• di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. =>"인접" : 상/하/좌/우 방향으로 붙어있다!

내가 작성한 코드 :

public static boolean dfs(int x,int y) {
	//기준점(x,y)에서 이동한 갯수가 4인지 확인! 한칸씩 이동할 때마다 1씩 증가!
	//4칸을 이동하기만 하면 true를 리턴.
		if(dist[x][y]==4) return true;
		c[x][y] = true;
		dist[x][y] = 0;//기준점은 거리가 0!
		for(int i=0;i<4;i++) {
			int nx = x+dx[i],ny = y+dy[i];
			if(nx<0 || nx>n-1 || ny<0 || ny>m-1) continue;
			if(a[nx][ny] == a[x][y] && c[nx][ny]==false) {
				dist[nx][ny] = dist[x][y]+1;
				dfs(nx,ny);
			}
		}
		return false;
	}

정답 코드 : 싸이클을 찾기만 하면되기 대문에 거리 개념은 필요가 없다. - dist 배열 삭제. 재귀함수를 계속해서 호출해서 마지막에 리턴되는 값을 가져온다. 반환형이 boolean!

bool go(int x, int y, int cnt, char color) {
    if (cnt == 4) return true;
    for (int k=0; k<4; k++) {
        int nx = x+dx[k], ny = y+dy[k];
        if (0 <= nx && nx < n && 0 <= ny && ny < m) {
            if (check[nx][ny] == false && a[nx][ny] == color) {
                if (go(nx, ny, cnt+1, color)) {
                    return true;
                }
            }
        }
    }
    return false;
}

하지만 위의 코드 역시 정답은 아니다. 싸이클이 존재하는지 판별하지 않기 때문이다. Solution#1. 현재 위치가 (x,y)일 때 방문했는지 확인하는 것에서 그치는 것이 아니라, 방문한 (x,y)이면 원래 좌표(x,y)에서부터 이동한 거리가 4이상인지 확인해준다.

bool go(int x, int y, int cnt, char color) {
    if (cnt == 4) {
        if(cnt-dist[x][y]>=4){//이동한 칸 갯수 - 기준점에서 (x,y)까지 거리 >=4
            return true;
        }
    }
    for (int k=0; k<4; k++) {
        int nx = x+dx[k], ny = y+dy[k];
        if (0 <= nx && nx < n && 0 <= ny && ny < m) {
            if (check[nx][ny] == false && a[nx][ny] == color) {
                if (go(nx, ny, cnt+1, color)) {
                    return true;
                }
            }
        }
    }
    return false;
}

Solution#2 . 이전에 방문한 노드를 재방문한다 = 싸이클이 생겼다는 의미! =>하지만, BFS나 DFS는 기본적으로 노드를 한번씩만 방문하기 때문에, 다음에 방문할 노드(next;nx,ny)는 현재 노드를 기준(x,y)으로 그 이전 노드(past;px,py)가 아니여야 한다!

=>거리 개념은 불필요하다. 거리가 얼마나 떨어져있는지는 중요하지 않기 때문이다.

import java.util.*;
public class TwoDots_4th_pastxy_cycle {
	public static boolean[][] c;
	public static char[][] a;
	public static int n;
	public static int m;
	public static int[] dx= {-1,1,0,0};
	public static int[] dy= {0,0,-1,1};
	public static boolean  dfs(int x,int y,int px,int py,char color) {
		if(c[x][y]) return true;//방문한 적이 있다면 true! 자세한 처리는 아래에서!
		c[x][y] = true;
		for(int i=0;i<4;i++) {
			int nx = x+dx[i],ny = y+dy[i];
			if(nx<0 || nx>n-1 || ny<0 || ny>m-1) continue;
			if(!(nx==px && ny==py)) {
				if(a[nx][ny]==color) {//이미 방문한 노드라도 방문해도 괜찮음. 싸이클 생성하는지 확인하는 것이 목표이니까!
					if(dfs(nx,ny,x,y,color)) return true;
				}
			}
		}
		return false;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();//행.
		m = sc.nextInt();//열.
		sc.nextLine();
		a = new char[n][m];
		c = new boolean[n][m];
		for(int i=0;i<n;i++) {
			String s = sc.nextLine();
			for(int j=0;j<m;j++) {
				a[i][j] = s.charAt(j);
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(c[i][j]) continue;
				boolean ok = dfs(i,j,0,0,a[i][j]);
				if(ok) {
					System.out.println("Yes");
					System.exit(0);
				}
			}
		}
		System.out.println("No");
	}

}