[JAVA]백준_1987_알파벳

문제링크

 

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

1987번: 알파벳

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int R,C;
	static char[][] map;
	static boolean isVisited[];
	static int maxLen = Integer.MIN_VALUE;
	static int len = 0;
	static int dx[] = {0,0,-1,1};
	static int dy[] = {-1,1,0,0};
	public static void main(String[] args) throws IOException {
		//A는 97 알파벳은 26개
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		map = new char[R][C];
		for(int i=0;i<R;i++) 
			map[i] = br.readLine().toCharArray();
		
/*		for(int i=0;i<R;i++)
			System.out.println(Arrays.toString(map[i]));*/
		/*for(int i=0;i<R;i++) {
			for(int j=0;j<C;j++) {
				getLength(i,j);
				System.out.println("("+i+","+j+") 위치에서의 max :"+maxLen);
			}
		}
		*/
		//getLength(0, 0);
		isVisited = new boolean[26];
		isVisited[map[0][0]-'A'] = true;
		dfs(0,0);
		System.out.println(maxLen);
	}
	
	private static boolean dfs(int row,int col) {
		//시작지점은 (0,0)
		//System.out.println("row:"+row+" col:"+col);
		//기저조건??
		for(int d=0;d<4;d++) {
			int nx = row + dx[d];
			int ny = col + dy[d];
			//System.out.println("nx :"+nx+" ny:"+ny);
			if(nx<0 || nx>=R || ny<0 || ny>=C || isVisited[map[nx][ny]-'A']) continue; //범위 벗어남
			
			isVisited[map[nx][ny]-'A'] = true;
			//System.out.println(map[nx][ny]);
			dfs(nx,ny);
			isVisited[map[nx][ny]-'A'] = false; //다음에 올 사람 위해서 false로 바꿔주기
		}
		len = 0;
		for(int i=0;i<26;i++)
			if(isVisited[i]) len++;
		maxLen = (maxLen<len)?len:maxLen;
		return false; //방향을 다 타고 들어갔지만 재귀를 타고 들어가지 못함
	}

/*	private static void getLength(int row,int col) {
		Queue<Node> q = new LinkedList<>(); //bfs 돌릴 큐
		isVisited = new boolean[26]; //방문했는지 안했는지
		
		q.offer(new Node(row,col)); //현재 값 넣어주기
		isVisited[map[row][col]-'A'] = true;
		int num = 1; //말이 지나는 칸은 좌측 상단의 값도 포함!
		
		while(!q.isEmpty()) {
			row = q.peek().x;
			col = q.peek().y;
			q.poll();
			for(int d=0;d<4;d++) {
				//사방 탐색
				int nx = row + dx[d];
				int ny = col + dy[d];
				
				if(nx<0 || nx>=R || ny<0 || ny>=C) continue; //범위 벗어나면 튀튀
				if(!isVisited[map[nx][ny]-'A']) {
					//현재 칸에 있는 알파벳이 지나치지 않은 곳이라면
					num++;
					isVisited[map[nx][ny]-'A'] = true; //방문 처리 해주고
					System.out.print(map[nx][ny]+" ");
					q.offer(new Node(nx,ny));
				}
				
			}
		}
		maxLen = maxLen<num?num:maxLen;
	}

	
	private static class Node{
		int x;
		int y;
		public Node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}*/
}

 

 

---

원래 BFS로 접근을 했었다.

근데 문제를 다시 보니 어짜피 한 곳에서만 출발하니까 굳이 모든 곳을 다 돌면서는 필요가 없을 것 같아서

DFS를 사용해서 풀어보았다.

 

중간에 주석처리한 부분은 접근 잘못했던 부분 남겨두었다. 물론 값도 정답이 아닌 답이 나온다.

 

간단하게 설명하자면

 

이 부분이 dfs함수이다.

기저조건을 주어야 할 것같아서 생각해보았는데 어짜피 isVisited가 다 차면 나올거같아서 따로 주진않았다.

그리고 기저조건을 어떻게 주어야할지 모르겠어서 채우지 않았다.

 

if문을 통해서 배열범위를 벗어나거나 들렀던 곳이면 방문하지 않도록 하였다.

그 후 dfs()를 통해서 탐색한다.

 

만약 for문을 벗어나면 4방향을 다 찾고서 나온 것이니 이제 더 이상 진행할 곳이 없다고 판단하여 길이를 구해주었다.

isVisited가 true인 만큼 알파벳을 방문한 것이니 true인 값을 세어주었다.