[백준] 1987 - 알파벳 (JAVA)

소요시간

20분 정도 걸렸다. 하지만 정답은 맞췄는데 소요 시간이 너무 길었고 중복탐색을 계속해서 하는 것을 알았다. 제출 했을 때 소요 시간이 3초였는데, 2초 이하로 줄여보도록 10분정도 더 풀어서 1초대로 줄이는데에 성공했다.

사용한 자료구조 & 알고리즘

dfs 의 개념과 백트래킹을 사용했다. 그리고 hash도 사용했는데 이미 한 번 사용한 알파벳은 해시에 넣어줌으로써 다음에 탐색할 단어는 hash에 없는 경우에만 탐색하도록 했다.

풀이과정

dfs 메소드가 작동할 때마다 count 값이 증가할 것이고, 가장 긴 count가 return 해주는 값이 될 것이다.
아까 말하였듯 Hash에 글자가 없는 경우에만 탐색하기 때문에 그것이 참임을 증명할 수 있다.

소스코드

import java.io.*;
import java.util.*;
import java.math.BigInteger;


public class Main{

	static char map[][];
	static int max=0;

	static int xx[]= {-1,1,0,0};
	static int yy[]= {0,0,-1,1};
	static boolean visited[][];
	static HashSet<Character> set=new HashSet<>();

	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int height=Integer.parseInt(st.nextToken());
		int width=Integer.parseInt(st.nextToken());

		map=new char[height][width];
		visited=new boolean[height][width];
		for(int i=0;i<height;i++) {
			String word=br.readLine();
			for(int j=0;j<width;j++) {
				map[i][j]=word.charAt(j);
			}
		}
		
		set.add(map[0][0]);
		dfs(0,0,1);
		
		System.out.println(max);

	}
	public static void dfs(int y,int x,int count) {
		max=Math.max(max, count);
	
		for(int i=0;i<4;i++) {
			int nextY=y+yy[i];
			int nextX=x+xx[i];
			if(nextY<0||nextX<0||nextY>=map.length||nextX>=map[0].length)
				continue;

			if(!set.contains(map[nextY][nextX])) {
				set.add(map[nextY][nextX]);
				dfs(nextY,nextX,count+1);
				set.remove(map[nextY][nextX]);
			}

		}

	}


}

결과

1. 처음에 중복 탐색을 했었던 코드
   

2. 중복 탐색을 제거한 코드

확실히 시간 차이가 난다. 하지만 더 짧게 할 수도 있다.

회고

다른 사람 풀이를 봤는데 나보다 1초 정도 더 빠르게 작동하는 사람도 있었다. 실제로 내 dfs 메소드를 보면 return 문이 없는데, return 문을 적절하게 섞어서 소요시간을 더 짧게 할 수도 있을 것 같다. 다음에 같은 주제의 백트래킹 문제가 주어진다면 return을 적절히 활용해야 겠다고 생각한다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.

https://solved.ac/profile/anwlro0212