백준- 1987 알파벳

www.acmicpc.net/problem/1987

1987번: 알파벳

---

같은 알파벳을 두번 지날수 없다

-> DFS로 탐색. String값을 들고다니며 contains메소드로 지나온 문자열을 체크해주려고 했음

 

결과: 메모리 초과

지금 생각해보면 String값은 매번 새로 복사해서 새로운주소에 저장해주어야하므로 메모리를 많이 쓸것 같았는데 역시나 통과가 안됐다. 

 

---

방문배열, 방문알파벳 배열을 사용하여 DFS탐색함.

---

import java.util.Arrays;
import java.util.Scanner;

public class Main {
/*
 * 말이 최대 몇칸? -> 다해본다 DFS
 * 4방탐색
 */
	static int R,C;
	static int[][] arr;
	static int dr[]= {-1,1,0,0};//상하좌우
	static int dc[]= {0,0,-1,1};
	static boolean visit[][];
	static boolean check[]= new boolean[26];//알파벳이 26글자이므로
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();//행값
		C = sc.nextInt();//열값
		arr = new int[R][C];
		visit = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			String str = sc.next();
			for (int j = 0; j < C; j++) {
				arr[i][j]= str.charAt(j)-'A';
                //A~Z를 int형으로 바꾸면 65~90. 따라서 -'알파벳'해줌
                //'A'-'A' =0. 
			}
		}
		//dfs
		visit[0][0]=true;//초기 방문체크
		check[arr[0][0]]=true;//초기값 true
		System.out.print(dfs(0,0));//좌측 상단에서 시작
	}

	private static int dfs(int r, int c) {
		int cnt=0;//몇번실행했는지 
		for (int d = 0; d < 4; d++) {
			int nr = r+dr[d];
			int nc = c+dc[d];

			if(nr>=0 && nr <R && nc>=0 && nc<C  && ! visit[nr][nc]) {//방문하지않았으면
				if(!check[arr[nr][nc]]) {//담은 알파벳이 아니라면
					visit[nr][nc]=true;//방문체크
					check[arr[nr][nc]]=true;//담음 체크
					cnt = Math.max(cnt, dfs(nr,nc));//dfs실행
					visit[nr][nc]=false;//백트레킹
				}
				
			}
		}
		check[arr[r][c]]= false;
		return cnt+1;//리턴시 값을 +1씩하여 총 실행횟수 리턴.
	}

	public static void print() {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				System.out.print(arr[i][j]+" ");
			}System.out.println();
		}
	}

}

---

결과