[백준] 1987번 알파벳 (DFS_JAVA)

BFS로 풀다가, 메모리 초과가 발생해서 검색해봤다.

 

DFS로 풀어야 하는 문제였다.

아 왜 DFS는 생각하지 못했을까!

DFS 연습을 많이 해야겠다 생각한 문제

 

---

문제

 

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

1987번: 알파벳

 

 

---

설계

 

알고리즘 설계[접근 방법] : DFS + 백트레킹

전형적인 DFS로 탐색하다가, 백트레킹을 해야하는 문제다.

알파벳 개수인 26개의 크기만큼 사용 체크 배열을 만들고, 사용했다면 더이상 탐색하지 않는 방법으로 백트레킹을 하면 된다.

BFS는 메모리 초과가 발생하는 이유는 한 발자국 움직일때마다 사용체크 배열을 복사해줘야 하기 때문이다. 하지만 DFS를 사용한다면, 다시 되돌아왔을 때 사용체크 배열을 false로 값을 바꾸기만 하면 된다.

 

풀이 과정

1.

배열의 크기를 입력받고, 2차원 배열을 생성한다.

 

2.

사방향 탐색을 할 배열 r, c를 만들고, 방문체크 배열 isvisited을 생성한다.

map[0][0]에서 출발하므로 map[0][0]의 알파벳을 사용했다고 표시한다.

 

3.

DFS 메서드에서는 현재 깊이인 depth가 max보다 크다면 max값을 갱신한다.

 

4.

사방향 탐색을 하면서 다음의 조건에 걸린다면 넘어간다.

- 탐색하는 위치가 배열 밖으로 벗어난다면 넘어간다.

- 현재 위치가 이미 사용한 알파벳이라면 넘어간다.

 

이 조건에 해당되지 않는다면, 현재 위치를 탐색해도 되는 것이다.

현재 위치의 알파벳을 사용했다고 표시하고 다음 DFS로 넘어간다.

 

5.

모든 탐색이 종료되고 현재 자리로 되돌아 왔을때, 사용했던 알파벳은 표시되면 안되기에 현재 알파벳의 사용 체크를 원상복구한다.

 

 

---

코드

 

import java.util.*;

public class Test_1987_알파벳 {
	
	static char[][] map;
	static boolean[] isvisited;
	static int[] r, c;
	static int max;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		map = new char[n][m];
		for(int i=0; i<n; i++) {
			map[i] = sc.next().toCharArray();
		}
		
		//사방향 탐색, 방문 체크 배열
		r = new int[] {-1, 0, 1, 0};
		c = new int[] {0, 1, 0, -1};
		
		isvisited = new boolean[26];
		isvisited[map[0][0]-'A'] = true;
		
		max = 0;
		DFS(0, 0, 1);
		
		//출력
		System.out.println(max);
	}
	
	//DFS
	public static void DFS(int i, int j, int depth) {
		
		if(max < depth) max = depth;
		
		//사방 탐색
		for(int k=0; k<4; k++) {
			int dr = i+r[k];
			int dc = j+c[k];
			
			//범위에 벗어나거나, 이미 사용한 알파벳일 경우 넘어가기
			if(!(0<=dr && dr<map.length && 0<=dc && dc<map[i].length)) continue;
			if(isvisited[map[dr][dc]-'A']) continue;
			
			//방문 체크 후 다음 단계
			isvisited[map[dr][dc]-'A'] = true;
			DFS(dr, dc, depth+1);
			
			//원상복구
			isvisited[map[dr][dc]-'A'] = false;
			
		}
	}
}

 

 

(❁´◡`❁)

끝!