[백준] code.plus(그래프 알고리즘,JAVA)16929번, Two Dots

문제 링크

16929번: Two Dots

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

이 문제에 핵심은

1. 사이클이 존재하면 Yes, 존재하지 않으면 No를 결과로 출력해야 한다.

2. 사이클이 지나는 점에 개수가 4개 이상이어야 사이클로 인정됩니다.

3. 사이클은 같은 색의 점으로만 이루어져야 합니다.

 

주어진 점들의 정보를 가지고 DFS(깊이 우선 탐색)을 진행하여 각 점들을 시작으로 탐색하여 사이클이 존재하는지 확인하였습니다.

 

사이클이 존재하면 바로 코드를 종료하고 Yes를 결과로 출력하였습니다.

 

사이클이 존재한다는 것은 시작 점으로 다시 돌아온다는 의미입니다.

 

예제입력1

점 (0, 0)의 값 A부터 사이클이 존재하는지 DFS 탐색을 시작합니다.

A	A	A	A
A	B	C	A
A	A	A	A

 

탐색은 상, 하, 좌, 우 순으로 탐색

 

A(↓)	A(←)	A(←)	A(←)
A(↓)	B	C	A(↑)
A(→)	A(→)	A(→)	A(↑)

 

DFS탐색으로 시작 지점(0, 0)으로 4개 이상의 점을 지나면서 돌아왔기 때문에 사이클이 존재합니다.

 

결과적으로 사이클이 존재하기 때문에 더이상 탐색을 하지않고 "Yes"를 결과로 출력합니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 dots Board 정보를 저장하였습니다.
• 각 점을 시작으로 DFS탐색을 통해 사이클이 존재하는지 확인하는 dfs함수를 실행하였습니다.
• 사이클이 존재하면 System.out.println() 이용하여 "Yes"을 출력하고 코드를 종료시켰습니다.
• 사이클이 존재하지 않으면 "No"을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs함수는 DFS로 탐색하여 4개 이상의 점을 지나는 사이클이 존재하는지 확인하는 함수입니다.
• dfs함수는 사이클이 발견되면 "Yes"를 결과로 출력한뒤 코드를 종료합니다.

 

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

public class Main{
	static int N,M, curX, curY;
	static char[][] dots;	//dots 보드 배열
	static int[] dx = {0, 0, -1, 1};	//상, 하, 좌, 우 x값 변경값
	static int[] dy = {-1, 1, 0, 0};	//상, 하, 좌, 우 y값 변경값
	static boolean[][] visited;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		dots = new char[N][M];
        	//dots 보드 저장
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<M;j++) {
				dots[i][j] = str.charAt(j);
			}
		}
        	//각 점을 시작으로 사이클이 존재하는지 DFS로 탐색
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				visited = new boolean[N][M];
				visited[i][j] = true;
				curX = j;
				curY = i;
				dfs(j,i, dots[i][j],1);
			}
		}
		bw.write("No\n");	//사이클 존재하지 않을 때 "No" BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//사이클이 존재하는지 확인하는 DFS 함수
	static void dfs(int x, int y, char dot, int count) {
		for(int i=0;i<4;i++) {
			int tempX = x + dx[i];	//x값 변경
			int tempY = y + dy[i];	//y값 변경
			if(tempX>=0 && tempX<M && tempY>=0 && tempY<N && dots[tempY][tempX] == dot) {
				if(!visited[tempY][tempX]) {
					visited[tempY][tempX] = true;
					dfs(tempX,tempY,dot,count+1);
				}else {
                			//점을 4개를 지나며 사이클일 때
					if(count>=4 && tempX==curX && tempY==curY) {
						System.out.println("Yes\n");	//"Yes" 결과 출력
						System.exit(0);			//코드 종료
					}
				}
			}
		}
		return;
	}
}