728x90
배열의 모든 원소에 대해 사방탐색을 6번 진행하는 것이다. dfs를 통해 구현하면 되는데, 한 번 방문한 원소도 다시 방문할 수 있으니 방문여부를 검사할 필요는 없다.
결과값의 중복을 제거하기 위해 hashSet을 사용하였다.
7개의 결과값을 담을 ans배열을 static으로 선언하여 depth가 1 증가할 때마다 ans[depth]에 수를 담았다.
모든 원소에 대해 dfs를 수행하고, ans배열의 0번 index에 초기값을 담아 진행한다.
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) {
ans[0] = arr[i][j];
dfs(arr, i, j, 1);
}
dfs는 사방탐색으로 한다.
먼저 깊이가 7이 되면 결과값을 return한다.
그 다음 사방탐색을 통해 nr과 nc과 배열의 인덱스 범위 안에 있으면 ans[depth]에 값을 추가하고 다시 depth를 1씩 늘려가며 dfs를 계속한다.
static void dfs(int[][] arr, int r, int c, int depth) {
if (depth == 7) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 7; i++)
sb.append(ans[i]);
set.add(sb.toString());
return;
}
// 사방탐색
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < 4 && nc >= 0 && nc < 4) {
ans[depth] = arr[nr][nc];
dfs(arr, nr, nc, depth + 1);
}
}
}
전체 코드
package d4;
import java.util.HashSet;
import java.util.Scanner;
public class SWEA_2819_격자판숫자 {
static HashSet<String> set = new HashSet<>();
static int cnt;
static int N = 4;
static int[] ans = new int[7];
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 1; t <= T; t++) {
int[][] arr = new int[4][4];
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
arr[i][j] = sc.nextInt();
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) {
ans[0] = arr[i][j];
dfs(arr, i, j, 1);
}
System.out.println("#" + t + " " + set.size());
set.clear();
}
}
static void dfs(int[][] arr, int r, int c, int depth) {
if (depth == 7) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 7; i++)
sb.append(ans[i]);
set.add(sb.toString());
return;
}
// 사방탐색
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < 4 && nc >= 0 && nc < 4) {
ans[depth] = arr[nr][nc];
dfs(arr, nr, nc, depth + 1);
}
}
}
}
728x90
'문제 풀이 > SWEA' 카테고리의 다른 글
[SWEA] 1767 - 프로세서 연결하기 (자바/Java) (1) | 2022.09.23 |
---|---|
[SWEA] 4008 - 숫자 만들기 (자바/Java) (0) | 2022.09.22 |
[SWEA] 1231 - 중위 순회 (0) | 2022.08.23 |
[SWEA] 1873 - 상호의 배틀 필드 (자바/Java) (0) | 2022.08.22 |
[SWEA] 1216 - 회문 2 (자바/Java) (0) | 2022.08.12 |