[백준] 1987 알파벳 - Backtracking(백트래킹) + DFS(깊이우선탐색) + HashSet(해시셋) JAVA

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

1987번: 알파벳

코드설명

DFS와 HashSet을 활용하여 해결합니다.

 

처음에 BFS로 착각하고 풀었습니다.

하지만, 문제조건을보면, 첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.는 조건이 있습니다.

한개의 말을 깊이우선탐색을 진행하여 진행해야한다는 문제라는것을 알 수 있습니다.

 

문제에서 유의해야할점들입니다.

1. HashSet을 순회하는방법

- HashSet같은경우 향상된 for문을 통해 순회할 수 있습니다.

for(Character a : currentHashSet) {
    newHashSet.add(a);
}

- HashMap같은경우 Map.entrySet을 통해 순회할 수 있습니다.  ( HashMap 또한 향상된 for문 사용은 가능 )

 

2. HashSet은 기본적으로 얕은복사입니다. 깊은복사를 하고싶다면 순회하여 진행합니다.

HashSet<Character> HashSet = new HashSet<Character>();
HashSet<Character> newHashSet = HashSet; //얕은복사 이루어집니다. ( 주소를 참조 )

하지만, 이 문제에서 깊은복사를 통하여 진행하면, 시간초과가 나므로 얕은복사를 통해 HashSet의 값을 재귀가 끝난뒤 빼주면서 진행합니다.

 

코드

하나의 HashSet으로 전역적으로 관리합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	public static int R, C;
	public static int answer = 0;
	public static char[][] map;
	public static HashSet<Character> hashset = new HashSet<>();
	public static int[] dx = {-1,1,0,0}, 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 char[R][C];
		for(int i=0;i<R;i++) {
			st = new StringTokenizer(br.readLine());
			String inputAlphabet = st.nextToken();
			for(int j=0;j<inputAlphabet.length();j++) {
				map[i][j] = inputAlphabet.charAt(j);
			}
		}
		
		hashset.add(map[0][0]);
		simulate(0, new Node(0, 0, 1));
		System.out.println(answer);
	}
	
	public static void simulate(int level, Node start) {
		answer = Math.max(answer, start.moved);
		if(level >= R*C) {
			return ;
		}
		
		for(int dir = 0; dir < 4; dir++) {
			int nr = start.r + dx[dir];
			int nc = start.c + dy[dir];
			
			if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
			if(hashset.contains(map[nr][nc]) == true) continue;
			
			hashset.add(map[nr][nc]);
			simulate(level + 1, new Node(nr, nc, start.moved + 1));
			hashset.remove(map[nr][nc]);
		}
		
		
	}
	
}
 
class Node{
	int r;
	int c;
	int moved;
	public Node(int r, int c, int moved) {
		this.r = r;
		this.c = c;
		this.moved = moved;
	}
}

 

정답코드 ( DFS로 진행, HashSet 새로 생성하는것이 아닌 재귀함수가 끝나고 추가해준것 삭제 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int R, C;
	public static char[][] arr;
	public static int answer = 0;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static boolean[][] visited;
    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());
    	
    	arr = new char[R][C];
    	visited = new boolean[R][C];
    	for(int i=0;i<R;i++) {
    		st = new StringTokenizer(br.readLine());	
    		arr[i] = st.nextToken().toCharArray(); 
    	}
    	
    	HashSet<Character> hashset = new HashSet<>();
    	hashset.add(arr[0][0]);
    	simulate(new Node(0,0, hashset, 1));
    	System.out.println(answer);
    	
    }
    public static void simulate(Node start) {
    	
    	int r = start.r;
    	int c = start.c;
    	int cnt = start.cnt;
    	HashSet<Character> currentHashSet = start.hashset;
    	
    	answer = Math.max(answer,  cnt);
    	
    	for(int dir = 0; dir < 4; dir++) {
    		int nr = r + dx[dir];
    		int nc = c + dy[dir];
    		int nCnt = cnt + 1;
    		if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
    		if(currentHashSet.contains(arr[nr][nc])) continue;
    		
    		currentHashSet.add(arr[nr][nc]);
    		Node nNode = new Node(nr, nc, currentHashSet, nCnt);
    		simulate(nNode);
    		currentHashSet.remove(arr[nr][nc]);
    	}
    	
    }
}
 
class Node{
	int r;
	int c;
	HashSet<Character> hashset;
	int cnt;
	public Node(int r, int c, HashSet<Character> hashset, int cnt) {
		this.r = r;
		this.c = c;
		this.hashset = hashset;
		this.cnt = cnt;
	}
}

 

DFS로 진행하여 답은 맞지만, 시간초과가 나는 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int R, C;
	public static char[][] arr;
	public static int answer = 0;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static boolean[][] visited;
    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());
    	
    	arr = new char[R][C];
    	visited = new boolean[R][C];
    	for(int i=0;i<R;i++) {
    		st = new StringTokenizer(br.readLine());	
    		arr[i] = st.nextToken().toCharArray(); 
    	}
    	
    	HashSet<Character> hashset = new HashSet<>();
    	hashset.add(arr[0][0]);
    	simulate(new Node(0,0, hashset, 1));
    	System.out.println(answer);
    	
    }
    public static void simulate(Node start) {
    	
    	int r = start.r;
    	int c = start.c;
    	int cnt = start.cnt;
    	HashSet<Character> currentHashSet = start.hashset;
    	
    	answer = Math.max(answer,  cnt);
    	
    	for(int dir = 0; dir < 4; dir++) {
    		int nr = r + dx[dir];
    		int nc = c + dy[dir];
    		int nCnt = cnt + 1;
    		if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
    		if(currentHashSet.contains(arr[nr][nc])) continue;
    		
    		HashSet<Character> newHashSet = new HashSet<>();
    		for(Character a : currentHashSet) {
    			newHashSet.add(a);
    		}
    		newHashSet.add(arr[nr][nc]);
    		Node nNode = new Node(nr, nc, newHashSet, nCnt);
    		simulate(nNode);
    	}
    	
    }
}
 
class Node{
	int r;
	int c;
	HashSet<Character> hashset;
	int cnt;
	public Node(int r, int c, HashSet<Character> hashset, int cnt) {
		this.r = r;
		this.c = c;
		this.hashset = hashset;
		this.cnt = cnt;
	}
}

 

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.는 조건이 있으므로 DFS로 한 말이 어디까지 갈 수 있는지 체크해야합니다.

처음에 BFS로 착각하고 푼 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int R, C;
	public static char[][] arr;
	public static int answer = Integer.MAX_VALUE;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static boolean[][] visited;
    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());
    	
    	arr = new char[R][C];
    	visited = new boolean[R][C];
    	for(int i=0;i<R;i++) {
    		st = new StringTokenizer(br.readLine());	
    		arr[i] = st.nextToken().toCharArray(); 
    	}
    	
    	simulate();
    	System.out.println(answer);
    	
    }
    public static void simulate() {
    	
    	Queue<Node> q = new LinkedList<>();
    	HashSet<Character> hashsetTemp = new HashSet<Character>();
    	hashsetTemp.add(arr[0][0]);
    	q.offer(new Node(0, 0, hashsetTemp));
    	answer = 1;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		HashSet<Character> hashset = temp.hashset;
    		
    		for(int dir = 0; dir < 4; dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
    			if(hashset.contains(arr[nr][nc]) == true) continue;
    			
    			answer += 1;
    			HashSet<Character> nHashSet = new HashSet<Character>();
    			for(Character a : hashset) {
    				System.out.println("a:"+a);
    				nHashSet.add(a);
    			}
    			System.out.println();
    			nHashSet.add(arr[nr][nc]);
    			q.offer(new Node(nr, nc, nHashSet));
    		}
    		
    	}
    	
    	
    }
}
 
class Node{
	int r;
	int c;
	HashSet<Character> hashset;
	public Node(int r, int c, HashSet<Character> hashset) {
		this.r = r;
		this.c = c;
		this.hashset = hashset;
	}
}