1987(HashSet vs Array)

 

알파벳 : https://www.acmicpc.net/problem/1987

참조한 숏코드 : https://www.acmicpc.net/source/26502969

 

 

개선한 점

1. 최초 편의를 위해 HashSet의 contains를 이용해 중복을 체크하던 부분을 Int Array로 대체함.

2. Path를 trace하기 위해 인자로 String을 조합하여 넘긴 부분을 Int로 대체함.

3. 최초 초기값을 dfs 밖에서 지정하고 넘겼던 부분을 없애고, dfs 진입시 곧바로 체크하도록 변경

 

 

개선한 코드 : 수행시간 (약 880ms)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int R, C;
	static char[][] map;
	private static boolean DBG = false;
	static int[] dup;
	static int LEN = 9;

	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 char[R][C];
		dup = new int[27];
		for (int i = 0; i < R; ++i) {
			String s = br.readLine();
			for (int j = 0; j < C; ++j) {
				map[i][j] = s.charAt(j);
			}
		}

		dfs(0, 0, 1);

		System.out.println(answer);

	}

	static int dy[] = { 0, 0, 1, -1 };
	static int dx[] = { 1, -1, 0, 0 };
	static int answer = Integer.MIN_VALUE;

	private static void dfs(int row, int col, int size) {
		
		dup[map[row][col]-'A']=1;		
		answer = Math.max(answer, size);
		
		for (int i = 0; i < 4; i++) {
			int nRow = row + dx[i];
			int nCol = col + dy[i];
			if (nRow >= 0 && nRow < R && nCol >= 0 && nCol < C && dup[map[nRow][nCol]-'A'] == 0) {				
				dfs(nRow, nCol, size+1);				
			}
		}
		dup[map[row][col]-'A']=0;
	}

}

 

 

최초 제출 코드 (수행시간 약 2500ms)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {

	static int R, C;
	static char[][] map;
	private static boolean DBG = false;
	static HashSet<Character> dup;
	static int LEN = 9;

	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 char[R][C];
		dup = new HashSet<>();
		for (int i = 0; i < R; ++i) {
			String s = br.readLine();
			for (int j = 0; j < C; ++j) {
				map[i][j] = s.charAt(j);
			}
		}

		dup.add(map[0][0]);
		dfs(0, 0, "" + map[0][0]);

		if (DBG)
			System.out.println(PATH);
		System.out.println(answer);

	}

	static int dy[] = { 0, 0, 1, -1 };
	static int dx[] = { 1, -1, 0, 0 };
	static int answer = Integer.MIN_VALUE;
	static String PATH = "";

	private static void dfs(int row, int col, String path) {
		if (DBG) {
			if (answer < path.length()) {
				PATH = path;
			}
		}
		answer = Math.max(answer, path.length());

		for (int i = 0; i < 4; i++) {
			int nRow = row + dx[i];
			int nCol = col + dy[i];
			if (nRow >= 0 && nRow < R && nCol >= 0 && nCol < C && !dup.contains(map[nRow][nCol])) {
				dup.add(map[nRow][nCol]);
				dfs(nRow, nCol, path + map[nRow][nCol]);
				dup.remove(map[nRow][nCol]);
			}
		}

	}

}