[SWEA] 2819. 격자판의 숫자 이어 붙이기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB 

SW Expert Academy

---

1. 문제요약

4x4 크기의 격자판에서 0~9사이 숫자가 적혀있을 때,

4방향으로 인접한 격자로 총 6번 이동한다. 각 칸의 적혀있는 숫자를 차례로 이어붙일 때

만들 수 있는 서로 다른 일곱 자리 수들의 개수를 출력한다.

격자판을 벗어나는 이동은 불가능하다.

2. 풀이

세 번의 시행착오가 있었다.

1. 처음에는 중복순열로 방향을 줄세워서 중복검사를 했다.

근데 이렇게 하면 중복순열로 7자리 다 뽑고 나서 격자판의 범위를 벗어나는지 일일이 체크해줘야 했기 때문에

테케는 나오는데 시간초과가 났다. (10개 중 3개 통과)

2. 또 dfs의 시간초과 늪에 빠질까봐 두려워서 bfs로 풀리나? 싶어서 풀어봤는데 나는 안풀렸다.

도착하는 최단시간을 구하는 문제면 bfs를 쓰는데, 이건 가능한 모든 경우를 봐야하므로 dfs가 적절한 것 같았다.

3. dfs로 7자리 뽑고 기저조건에서 list 안의 값과 다르면 list에 넣어주고 같은게 있으면 바로 return하여 list의 size를 ans로 출력했다. 근데 또 시간초과가 났다.  (10개 중 4개 통과) 

 

결국 솔루션을 찾아봤는데

해답은 HashSet이었다. 

HashSet은 hashCode()와 equals() 메소드를 이용해서 추가한 순서를 유지하며 중복값을 저장하지 않는다.

(애초에 중복체크해서 중복있으면 저장을 안하는건가?)

 

사용 방법은 간단하다.

HashSet<String> set = new HashSet<> ();

set.add(문자열);

=> set이 알아서 중복값을 걸러주고 저장한다.

 

3. 코드

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

public class SW_2819_격자판숫자이어붙이기 {

	static int ans, sy, sx;
	static int[] tgt;
	static int[][] map;
	static HashSet<String> set;
	
	static int[] dy= {-1,1,0,0};
	static int[] dx= {0,0,-1,1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		
		for (int tc=1; tc<=T; tc++) {
			map = new int[4][4];
			set = new HashSet<> ();
			
			for (int i=0; i<4; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j=0; j<4; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			} //입력 완
			
			ans = 0;
			solution();
			ans = set.size();
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void solution() {
		for (int i=0; i<4; i++) {
			for (int j=0; j<4; j++) {
				sy=i;
				sx=j;
				String start = Integer.toString(map[i][j]);
				dfs(i, j, 1, start);
			}
		}
	}
	
	static void dfs(int y, int x, int d, String res) {
		if (d==7) {
			set.add(res);
			return;
		}
		
		for (int dir=0; dir<4; dir++) {
			int ny=y+dy[dir];
			int nx=x+dx[dir];
			if (ny<0||ny>=4||nx<0||nx>=4) continue;
			
			dfs(ny, nx, d+1,res+map[ny][nx]);
		}
	}
	
}

4. 사담

더 많이 풀어보자 갈 길이 참 멀구나..

hashset이라는 새로운 자료구조를 알았다 중복제거니까 앞으로 유용하게 써먹을 듯