[JAVA] 백준 1987 알파벳 풀이

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

---

풀이 방법

1. 시작 위치에서 사방탐색, 방문하지 않은 알파벳이 있다면 count++ && 진출하고 계속 탐색 (DFS)

2. 만약, 재귀가 끝났다면 count와 max 값을 비교

3. 재귀가 끝난 후, 다시 되돌아 가면서 방문했던 알파벳을 false로  && count 값 -1 

파란색: 방문한 곳, 빨간색: 최대경로

틀렸던 부분 & 주의할 부분 

1. 되돌아갈 때 count -1 을 꼭 해주어야 함 

2. 되돌아 갈 때 조건의 위치!! 

 

JAVA 코드

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

public class BOJ_1987_알파벳 {
	static StringTokenizer st;
	static StringBuilder sb=new StringBuilder();
	static int R,C;
	static char[][] map;
	static boolean[] visited;
	static int[][] dir= {{0,1},{1,0},{0,-1},{-1,0}}; //상하좌우
	static int max,cnt;
	static boolean[][] map_visited;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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++) {
			String str=br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j]=str.charAt(j);
			}
		}
		visited=new boolean [26]; 
		map_visited=new boolean[R][C];
		max=Integer.MIN_VALUE;
		// 무조건 한번은 방문하므로
		cnt=1;
		find(0,0);
		System.out.println(max);
	}
	private static void find(int x, int y) {

		visited[map[x][y]-65]=true;
		map_visited[x][y]=true;
//		System.out.println(map[x][y]+" 방문");
		
		for(int d=0; d<4; d++) {
			// 사방탐색
			int nx=x+dir[d][0];
			int ny=y+dir[d][1];
			if (isOkay(nx,ny)) {
				// 범위 벗어나지 않고, 방문하지 않았다면 
				if(visited[map[nx][ny]-65]==false && map_visited[nx][ny]==false) {
					cnt++;
					find(nx,ny);
				}
			}
		}
		// 갈 수 있는 곳 모두 탐색
		max=max<cnt?cnt:max;
		// 되돌아 가기 위해 cnt-1, 방문한 곳들 false로
		cnt--;
		visited[map[x][y]-65]=false;
		map_visited[x][y]=false;
	}
	private static boolean isOkay(int r, int c) {
		return r>=0 && c>=0 && r<R && c<C;
	}

}

백트래킹 문제를 몇번 풀어보니 이제 조건의 위치가 어느정도 감이 오는거같다.........? 

되돌아 갈 때, 방문한 곳을 false로 해주고 count 값을 -1 해줘야 하는 부분에서 한번에 떠오르지 않아 시간이 꽤 걸렸다.

빵집 문제와 비슷한 문제같다. 

2021.08.20 - [알고리즘/백준 BOJ] - [JAVA] 백준 3109 빵집 풀이