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

코드

/**
 * 보충수업 0822
 * 2819 격자판의 숫자 이어붙이기
 * 서로 다른 일곱자리의 수들의 개수를 구하는 문제
 * bfs로 4방 탐색으로 펼쳐지는데 대신 방문 표시를 하지 않는다.
 * 왜냐하면 한번 거쳤던 격자칸을 다시 거쳐도 되기 때문이다.
 * 출발 또한 임의의 위치에서 출발..
 * 
 * 4^2 * 4^6 = 4^8 = 2^16= 64,000가지
 * set -> treeset:정렬을 자주 할 때 유리 O(logN) / hashset : 검색을 많이 할때 유리 O(1)
 * map -> treeMap / hashMap 
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_2819 {

	private static HashSet<String> hs;
	private static char[][] m;

	public static class Point{
		int x, y;
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		int tc =Integer.parseInt(st.nextToken());
		for(int t = 1; t <= tc; t++ ) {
			m = new char[4][4];
			for (int i = 0; i < 4; i++) {
				String s = br.readLine();
				for (int j = 0, index = 0; j < 4; j++, index+=2) {
					m[i][j] = s.charAt(index);
				}
			}//입력완료
			hs = new HashSet<>();
			for(int r = 0; r < 4; r++) {
				for(int c =0; c <4; c++) {
					go(r,c,1,"");
				}
			}
			sb.append("#").append(tc).append(" ").append(hs.size()).append("\n");		
	}//end of testcase
		System.out.println(sb.toString());
} // end of main
	public static int dx[] = {0, 1, 0, -1};
	public static int dy[] = {1, 0, -1, 0};
	private static void go(int r, int c, int step, String str) {
		if(r < 0 || r >= 4 || c < 0 || c >= 4) return; //범위 체크
		str += m[r][c];//글자 이어 붙이기 
		if(step == 7) {	//7 글자니 ?
			if(!hs.contains(str)) { //중복되지 않았으면, 카운팅, 추가
				hs.add(str);
			}
			return;
		}
		//재귀 상하좌우 호출 
		for(int i = 0; i < dx.length; i++) {
			go(r + dx[i], c + dy[i], step +1, str);
		}
	}
}//end of class

수정한 코드

• String으로 이어 붙이는 코드보다 메모리를 줄이기 위해 수정함

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

public class Solution_2819_이광용 {

	private static HashSet<Integer> hs;
	private static int[][] m;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		int tc =Integer.parseInt(st.nextToken());
		for(int t = 1; t <= tc; t++ ) {
			m = new int[4][4];
			for (int i = 0; i < 4; i++) {
				String s = br.readLine();
				for (int j = 0, index = 0; j < 4; j++, index+=2) {
					m[i][j] = s.charAt(index) - '0';
				}
			}//입력완료
			hs = new HashSet<>();
			for(int r = 0; r < 4; r++) {
				for(int c =0; c <4; c++) {
					go(r,c,1, 0);
				}
			}
			sb.append("#").append(t).append(" ").append(hs.size()).append("\n");		
	}//end of testcase
		System.out.println(sb.toString());
} // end of main
	public static int dx[] = {0, 1, 0, -1};
	public static int dy[] = {1, 0, -1, 0};
	private static void go(int r, int c, int step, int num) {
		if(r < 0 || r >= 4 || c < 0 || c >= 4) return; //범위 체크
		num = num *10 + m[r][c];//글자 이어 붙이기 
		if(step == 7) {	//7 글자니 ?
			if(!hs.contains(num)) { //중복되지 않았으면, 카운팅, 추가
				hs.add(num);
			}
			return;
		}
		//재귀 상하좌우 호출 
		for(int i = 0; i < dx.length; i++) {
			go(r + dx[i], c + dy[i], step +1, num);
		}
	}
}//end of class