백준 : 16929

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

16929번: Two Dots

 

1. DFS 탐색은 바로직전 DFS 방향으로 갈수 없다.
2. 같은 문자가 아니면 갈수없다.
3. DFS 바운마다 visit처리를한다.
4. 만약 다음 칸이 visit 처리가됬고 현재 문자와 같은 문자면 ans 값을 성공으로 바꾼다.

 

1. 번처리는 방향을 

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

 

이런식으로 처리한다면 (d+2)%4 는 반대방향인것을 확인 할 수있다.

 

package 삼성;

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

public class TwoDots {
	// 소요시간 32분

	static int dy[] = { 1, 0, -1, 0 };
	static int dx[] = { 0, 1, 0, -1 };
	static int N, M;
	static char map[][];
	static boolean visit[][];
	static boolean ans;

	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());
		ans = false;
		map = new char[N][M];
		visit = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (visit[i][j])
					continue;
				DFS(i, j, -1);
			}
		}

		System.out.println(ans ? "Yes" : "No");
	}

	public static void DFS(int y, int x, int pd) {
		visit[y][x] = true;

		for (int d = 0; d < 4; d++) {
			if (pd == d)
				continue;
			int ny = dy[d] + y;
			int nx = dx[d] + x;
			if (ny < 0 || nx < 0 || ny >= N || nx >= M)
				continue;
			if (map[ny][nx] != map[y][x])
				continue;
			if (visit[ny][nx] && map[y][x] == map[ny][nx]) {
				ans = true;
			}

			if (visit[ny][nx])
				continue;
			DFS(ny, nx, (d + 2) % 4);
		}
	}

}