[백준 16929] Two Dots(Java)

1. 문제

www.acmicpc.net/problem/16929

16929번: Two Dots

2. 풀이

3. 코드

import java.io.*;
import java.util.*;

public class Main {

	static int N,M;
	static char[][] map;
	static boolean[][] visited;
	static int result;
	static int[][]dir = {{-1,0},{0,1},{1,0},{0,-1}};
	static int[][]cnt;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//br = new BufferedReader(new StringReader(src));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		visited = new boolean[N][M];
		cnt = new int[N][M];
		for(int i =0; i<N; i++) {
			String str = br.readLine();
			for(int j =0; j<M; j++) {
				map[i][j]= str.charAt(j);
			}
		}
		for(int i =0; i<N; i++) {
			for(int j =0; j<M;j++) {
				if(dfs(i,j,1,map[i][j])) {
					System.out.println("Yes");
					return;
				}
			}
		}
		
		System.out.println("No");
		
	}
	static boolean dfs(int r, int c, int length, char color) {
		if(visited[r][c]) {
			return length-cnt[r][c]>=4;
		}
		
		visited[r][c] =true;
		cnt[r][c] = length;
		for(int d =0; d<dir.length; d++) {
			int newR = r +dir[d][0];
			int newC = c +dir[d][1];
			if(isRange(newR, newC) && map[newR][newC]==color) {
				if(dfs(newR, newC, length+1, color)) {
					return true;
				}
			}
		}
		return false;
	}
	static boolean isRange(int r, int c) {
		return r>=0 && c>=0 && r<N && c<M; 
	}
	



	static String src = 
			"3 4\r\n" + 
			"AAAA\r\n" + 
			"ABCA\r\n" + 
			"AAAA";
}

반응형