import java.util.Scanner;
import java.io.FileInputStream;
class Solution {
static boolean[] visited;
static char[] sChar;
static int result;
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T;
T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
String s = sc.next();
char[] arr = new char[s.length()];
visited = new boolean[s.length()];
sChar = new char[s.length()];
result = 0;
for (int i = 0; i < s.length(); i++) {
arr[i] = s.charAt(i);
}
if (Integer.parseInt(s)<10 || s.equals("1000000")) { //예외처리 1의자리 수와 10^6인 백만
System.out.println("#" + test_case + " impossible");
} else {
//dfs
dfs(0, s.length(), arr); //0 , 문자열길이 , 배열
if (result == 1) {
System.out.println("#" + test_case + " possible");
} else {
System.out.println("#" + test_case + " impossible");
}
}
}
}
public static void dfs(int level, int cur, char[] original) { // 0 , 6, 142587
String num = "";
String oriNum = "";
if (level == cur) { //레벨을 이용히여 현재 트리 단계가 가장 아래에 오기까지 기다림
for (int i = 0; i < original.length; i++) {// dfs 돌리고 나서 만들어진 수를 String 형으로 만들어줌
num += sChar[i];
oriNum += original[i];
}
if (!num.equals(oriNum) && Integer.parseInt(num) % Integer.parseInt(oriNum) == 0) { //만들어진 수가 원래 수가 아니고 만들어진 수를 원래 수로 나눴을 때 나머지가 0이면 배수이므로
// result에 1넣기
result = 1;
}
}
for (int i = 0; i < original.length; i++) { // 문자열의 길이 만큼 for문 돌리기
if (visited[i] != true) {
visited[i] = true;
sChar[level] = original[i]; // 문자열을 트리의 깊이에 따라 하나 씩 더해 주기
dfs(level + 1, cur, original); // dfs 재귀를 돌 때마다 level에 1을 더해줌으로써 트리의 깊이를 아래로 늘려줌
visited[i] = false; //dfs가 재귀를 끝내고 나올 떄 visited를 false로 반환해주면서 다음 단계로 진행
}
}
}
}
Java
복사
DFS 함수의 매개 변수로 level을 주는데 이는 트리의 깊이다.
한번 씩 돌때마다 트리의 깊이에다가 +1 을 해줌으로써 다음 깊이로 들어갈 수 있게하는게 포인트.
그리고 DFS를 트리 가장 아래까지 돌고 나올 때 각 인덱스 마다 visited 함수를 false로 반환 함으로써, 다음 경로를 찾을 때, visited배열을 false로 초기화 한 상태에서 사용하게 한다.
같은 태그의 다른 글 보기
Search
