BOJ_1987_알파벳

1.

구분: 백트래킹, DFS, BFS, 그래프 탐색

언어: Java

전략:

• DFS로 탐색을 하는데, 특정 조건에 대해 pruning과정을 진행한다. 
• 특정 조건은 이미 방문한 경우이다(알파벳 중복 방지) 
• 알파벳을 방문 처리를 하고, 재귀를 부르고, 그 후에 다시 방문 해지를 해야 한다. 

---

• 2. 코드

package com.ssafy.hw;

import java.util.Scanner;

public class BOJ_1987 {

	static int r, c, cnt;
	static char[][] map;
	static boolean[] check;
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		r= scanner.nextInt();
		c = scanner.nextInt();
		map = new char[r][c];
		for(int i = 0; i<r; i++) {
			String str = scanner.next();
			for(int j = 0; j<c; j++) {
				map[i][j] = str.charAt(j);
			}
		}
        //알파벳의 방문여부를 체크하는 배열
		check = new boolean[26];
		max = -1;
		move(0,0,1);
		
		System.out.println(max);
		

	}//main
	
	static int max;
	//A-17     map[y][x]-'0'-17이 인덱스 A가 인덱스 0
	private static void move(int y, int x, int cnt) {
	
		//-'A'를 뺴면 내가 원하는 값을 얻을 수 있다. 
		int index = map[y][x] -'0'-17;
        //이 부분은 맨 처음을 위한 부분 - 위로 옮겨도 될듯
		check[index] = true;
		
		//만약 전체를 다 돌아서 이미 넘어버리면 그만해 
		//필요가 없다 이미 다 돌아서 이미 없으니까 아래에서 재귀가 호출되지 않는다
		if(cnt>r*c) {
			return;
		}
		
		
		max = cnt>=max? cnt:max;
		
		
		//4방탐색
		for(int i = 0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			//범위 벗어나면
			if(nx<0 || ny<0|| nx>=c|| ny>=r) continue;
			//이미 방문하면 
			int idx = map[ny][nx] -'0'-17;
			if(check[idx]) continue;
			
			check[idx] = true;
			move(ny, nx, cnt+1);
			check[idx] = false;
		}
		
	}//move
	
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};

}

---

3.

• index를 구하는 과정이 번거롭다 -> map[i][j] - 'A'를 통해 내가 원하는 값을 얻을 수 있다. 
• move함수에서 cnt가 전체 알파벳 개수보다 큰 경우는 고려하지 않아도 된다. 왜냐하면 이미 이 경우에 방문 처리가 되어있으니 어차피 밑에서 재귀가 불릴 수 없다. (단! 이 문제만 이러하지 다른 문제는 또 다를 수 있다.)