[백준/DFS] 1987: 알파벳 - 자바

문제

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

1987번: 알파벳

 

풀이

0,0 좌표부터 시작하여 중복되지 않은 알파벳을 탐색하여 가장 긴 길이를 구하는 문제이다.

처음에는 단순하게 DFS 탐색을 하며 탐색했던 알파벳을 List에 넣어서 새로운 좌표를 탐색할 때마다 List에 알파벳이 중복되는지 검사하였다. 그런데 이렇게 하면 시간초과가 발생하여 통과하지 못한다.

 

그렇다면 어떻게 접근하면 좋을까? 

내 생각은 List에 넣고서 contain 사용해 있는지 탐색하였는데 알파벳이 많아질수록 시간복잡도가 늘어나서 그런것 같다.

list의 시간복잡도는 o(n)이다. 또 다르게 아래 시간초과 풀이에서 ArrayDeque를 사용해 알파벳이 있는지 탐색했는데 이 과정도 o(n)이 소요되서 그런 것 같다.

 

알파벳 개수만큼의 check 배열을 만들고 알파벳이 입력되었을 때 해당 원소를 true값으로 만들어 중복된 알파벳인지 체크하였고 시간초과 없이 통과하였다. 

 

풀이 (시간초과)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int R, C;
	static char[][] map;
	static List<Character> check;
	static boolean[][] checkArea;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	static int max;
	
	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		input();
		Deque<Character> check = new ArrayDeque<Character>();
		solution(0, 0, 0, check);
		bw.write(String.valueOf(max));
		bw.flush();
		bw.close();
	}
	
	public static void solution(int r, int c, int cnt, Deque<Character> check) {
		if (check.contains(map[r][c])) {
			max = Math.max(max, cnt);
			checkArea[0][0] = false;
			return;
		} else {
			checkArea[r][c] = true;
			check.offer(map[r][c]);
			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) continue;
				if(checkArea[nr][nc] == true) continue;
				solution(nr, nc, cnt + 1, check);
			}
			checkArea[r][c] = false;
			for (int i = 0; i < check.size(); i++) {
				if(check.peekLast() == map[r][c]) {
					check.pollLast();
				}
			}
		}
	}
	
	public static void input() throws IOException {
		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];
		max = Integer.MIN_VALUE;
		for (int i = 0; i < R; i++) {
			String input = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = input.charAt(j);
			}
		}
		checkArea = new boolean[R][C];
	}
}

 

풀이 (정답)

import java.io.*;
import java.util.*;

public class Main {
	static int r,c;
	static int[][] map;
	static boolean[] checked;
	static int max=0;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	public static void main(String[] args) throws IOException{
		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 int[r][c];
		checked = new boolean[26];
		for(int i=0; i<r; i++) {
			String[] line = br.readLine().split("");
			for(int j=0; j<line.length; j++) {
				String alpha = line[j];
				map[i][j] = alpha.charAt(0)-'A';
			}
		}
		dfs(0,0,0);
		System.out.println(max);
	}
	
	static void dfs(int x, int y, int cnt) {
		if(checked[map[x][y]]) {
			max = Math.max(max, cnt);
			return;
		}
		else {
			checked[map[x][y]] = true;
			for(int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
			
				if(nx<0 || ny <0 || nx >r-1 || ny > c-1) continue;
				dfs(nx, ny, cnt+1);
			}
			checked[map[x][y]] = false;
		}
	}
}