백준 16929번: Two Dots

문제

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

16929번: Two Dots

---

풀이

Two Dots는 Playdots, Inc. 에서 만든 게임으로 같은 색으로 이루어진 사이클을 찾는 게임입니다.

이 게임에서 대각선으로는 움직일 수 없을 때 최소 4개의 점을 잇는 사이클이 존재하는지 여부를 확인하는 문제입니다.

---

접근

오른쪽으로 갔다가 바로 왼쪽으로 오면 2개의 점으로 사이클이 만들어지기 때문에 문제 조건에 부합합니다.

따라서 처음에는 dfs 함수 내부의 매개변수에서 깊이를 뜻하는 dpth가 2보다 크며 출발하는 점의 위치로 돌아왔을 때를 체크하는 방향으로 접근했었습니다.

하지만 위의 방식은 출발하는 점의 위치를 바꾸며 함수를 실행할 때마다 방문 여부를 확인해주는 visited 배열을 초기화해주고 모든 점을 전부 탐색해야 했기 때문에 비효율적이라는 생각이 들었습니다.

그래서 dfs 함수 내부의 매개변수에서 직전에 이동했던 방향을 뜻하는 pi와 반대되는 방향으로 이동하지 않을 때만 함수를 재귀적으로 실행하며 방문했던적이 있으면 사이클이 존재한다는 것을 확인할 수 있는 방향으로 접근했습니다.

---

코드

자바

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

public class Main {

    static int n, m;
    static char[][] arr;
    static boolean[][] visited;

    public static void dfs(int x, int y, int pi) {
        visited[x][y] = true;
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };
        for (int i = 0; i < 4; i++) {
            if (pi != i && pi % 2 == i % 2) continue; // (2)
            int nx = x + dx[i], ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m && arr[x][y] == arr[nx][ny]) { // (3)
                if (visited[nx][ny]) {
                    System.out.println("Yes");
                    System.exit(0);
                }
                dfs(nx, ny, i);
            }
        }
    }

    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());
        arr = 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++) {
                arr[i][j] = str.charAt(j);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) { // (1)
                    dfs(i, j, -1);
                }
            }
        }
        System.out.println("No"); // (4)
    }
}

(1) 해당 위치(i, j)에 방문한적 있는지 확인합니다.

dfs 함수를 통해 현재 위치와 같은 색으로 되어있고 연결돼있는 점들은 모두 방문처리를 하기 때문에 visited[i][j]가 true라면 다시 탐색할 의미가 없습니다. 따라서 false인 경우에 dfs함수를 실행하며 이때 방향을 0에서 3까지의 숫자로 표현하기 때문에 pi는 움직이지 않았다는 의미로 -1을 넣습니다.

 

(2) 해당 위치(x, y)에 방문처리를 한 뒤에 i를 포함한 for문 안에서 직전 방향 pi와 이동하려는 방향 i을 비교합니다.

pi와 i가 같지 않고 2로 나눴을 때의 나머지가 같다면 직전 방향과 반대 방향, 즉 왔던 곳으로 돌아가는 것이므로 넘어갑니다.

 

(3) 다음으로 이동할 수 있는 위치의 점의 색깔이 같으면 다음 과정을 실행합니다.

다음 위치는 (2)번 과정에 의해 직전의 위치와 같지 않으며 다음 위치를 방문한 적이 있다면 사이클이 발생한 것이므로 "Yes"를 출력한 뒤에 프로그램을 종료합니다.

방문한 적이 없다면 dfs 함수를 재귀적으로 실행하며 이때 pi는 이동한 방향인 i가 들어갑니다.

 

(4) 모든 과정이 끝나면 사이클이 존재하지 않는다는 뜻이기 때문에 "No"를 출력한 뒤에 프로그램을 종료합니다.

만약 사이클이 존재했다면 (3)번 과정에서 이미 프로그램이 종료됐을 것입니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n, m, **visited;
char **arr;
void dfs(int x, int y, int pi) {
	visited[x][y] = 1;
	int dx[] = { -1, 0, 1, 0 };
	int dy[] = { 0, -1, 0, 1 };
	for (int i = 0; i < 4; i++) {
		if (pi != i && pi % 2 == i % 2) continue;
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m && arr[x][y] == arr[nx][ny]) {
			if (visited[nx][ny]) {
				printf("Yes");
				exit(0);
			}
			dfs(nx, ny, i);
		}
	}
}
main() {
	scanf("%d %d", &n, &m);
	arr = (char**)malloc(sizeof(char*) * n);
	visited = (int**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++) {
		arr[i] = (char*)malloc(sizeof(char) * m);
		visited[i] = (int*)malloc(sizeof(int) * m);
		memset(visited[i], 0, sizeof(int) * m);
		scanf("%s", arr[i]);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j]) {
				dfs(i, j, -1);
			}
		}
	}
	printf("No");
}

자바를 이용한 풀이와 동일합니다.

 

---

결론

처음에 생각했던 접근 방식으로 작성한 코드는 아래와 같습니다.

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

public class Main {

    static int n, m, lx, ly;
    static char[][] arr;
    static boolean[][] visited;

    public static void dfs(int dpth, int x, int y) {
        visited[x][y] = true;
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };
        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 && arr[x][y] == arr[nx][ny]) {
                if (!visited[nx][ny]) {
                    dfs(dpth + 1, nx, ny);
                } else if (dpth > 2 && nx == lx && ny == ly) {
                    System.out.println("Yes");
                    System.exit(0);
                }
            }
        }
    }

    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());
        arr = new char[n][m];
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited = new boolean[n][m];
                lx = i; ly = j;
                dfs(0, i, j);
            }
        }
        System.out.println("No");
    }
}

틀린 답은 아니지만 위에서 설명한 바와 같이 여러모로 비효율적인 코드라고 생각합니다.