아래와 같은 배열이 있을 때, 1부터 탐색했을 때 탐색하는 모든 경로가 나오게 하라
int[][] arr = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3,7}, {4,8}, {4,9}, {5,10}};
→즉, 아래와 같은 답이 나오도록 출력.
`{1,2,4,8} , {1,2,4,9} {1,2,5,10}, {1,3,6}, {1,3,7}`
Class{
static List<List<Integer>> adjList = new ArrayList<>();
static boolean[] visited;
static List<List<Integer>> answer = new ArrayList<>();
public static void main(String[] args) {
int[][] arr = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,7},{4,8},{4,9},{5,10}};
1
2 3
4 5 6 7
8 9 10
//양방향 그래프가 아닌 단방향 그래프다.
for(int i=0; i<arr.length; i++){
adjList.add(new ArrayList<>()); // 리스트안에 하나의 노드역할을 하는 내부리스트 노드 개수만큼 생성
}
for(int[]a : arr){
adjList.get(a[0]).add(a[1]);
}
-->이중배열 arr을 보면 각 요소간의 연결을 나타냈다. 예를 들어, arr의 내부배열인 {1,2}는 1번과 2번이 연결.
따라서 내부배열의 0번째인덱스의 값을 리스트의 인덱스로하고, 내부배열의 1번째 인덱스 값을
리스트에 추가하면 각각의 리스트에 연결된 노드들이 담기게 된다.
List<Integer> temp =new ArrayList<>(); //answer안에 들어가는 내부리스트
dfs(1,temp);
System.out.print(answer);
}
static void dfs(int start,ArrayList temp){
temp.add(start);
if(adjList.get(a).isEmpty()){ //더이상 연결된 요소가 없을 때 dfs를 종료
answer.add(new ArrayList<>(temp);
return;
}
for(int a : adjList.get(start)){
if(!visited(a)){
visited[a] = true;
dfs(a,temp);
temp.remove(temp.size()-1); //리턴되었을 때 마지막요소를 제거 하고 다시 탐색들어가야하니까.(백트래킹)
}
}
}
--> dfs(1,temp)를 실행하면,
1.처음에 temp ={1}. 1과 연결된 2,3 중 먼저 2를 매개변수로 하여 dfs(2,temp={1}) 재귀호출
2.temp에 2추가 되고, 2와 연결된 4,5 중 먼저 4를 매개변수로 하여 dfs(4,temp={1,2}) 재귀호출
3.temp에 4추가 되고, 4와 연결된 8,9 중 먼저 8을 매개변수로 하여 dfs(8,temp={1,2,4})재귀호출
4.temp에 8추가 되고, 8과 연결된 요소가 없기 때문에 if문 충족 {1,2,4,8}을 answer의 첫번째에 붙이고 리턴
5.3번에서 재귀완료된 상태로 리턴되어 temp={1,2,4,8}에서 마지막 요소 제거하여 {1,2,4}
6.그런 다음 9를 매개변수로 하여 dfs(9,temp={1,2,4})재귀호출
7.temp에 9추가 되고, 9와 연결된 요소가 없기 때문에 if문 충족 {1,2,4,9}를 answer의 두번째에 붙이고 리턴
8.6번에서 재귀완료된 상태로 리턴되어 temp={1,2,4,9}에서 마지막 요소 제거하여 {1,2,4}
그런데 8,9 모두 재귀완료 되었기 때문에 3번도 자연스럽게 완료하여 2번에서 재귀완료된 상태로 리턴
그러면 마지막 요소 제거되어 temp={1,2}그리고 4,5중에서 남은 5를 매개변수로 하여 dfs(5,temp={1,2})재귀 호출
9.temp에 5추가 되고, 5와 연결된 10을 매개변수로 하여 dfs(10,temp={1,2,5})재귀호출
10.temp에 10추가 되고, if문 충족하여 answer에 {1,2,5,10} 붙이고 리턴.
11.9번에서 재귀완료된 상태로 리턴 되어 마지막 요소 제거 즉, temp={1,2,5}.
재귀를 다돌았기 때문에 5를 매개변수로 dfs호출했던 2번도 재귀완료되어 마지막 요소 제거 되어 temp={1,2}
그리고 2번도 재귀다 완료 했기 때문에 제일 처음 1번 상태로 리턴. 마지막 요소 제거되어 temp={1}
12. 1번상태로 돌아왔고, 2번 매개변수로하여 재귀완료했으니 남은 3을 매개변수로 하여 재귀호출하여
같은 방식으로 {1,3,6},{1,3,7}도 출력되는 것
ex.k=80(현재피로도), dungeons={{80,20},{50,40},{30,10}}.
Class Solution{
static static_k; //문제에서 주어지는 현재피로도를 dfs메서드 안에서도 공유하기 위해 클래스변수로 선언
static boolean[] visited; //마찬가지로 dfs메서드 안에서도 공유하기 위해
static int static_count; //마찬가지로 dfs메서드 안에서도 공유하기 위해
static int answer; //마찬가지로 dfs메서드 안에서도 공유하기 위해
public int soulution(int k, int[][] dungeons){
static_k = k; //문제에서 주어진 k를 공유되는 static_k에 대입
visited= new boolean[dungeons]// 어떤 던전을 방문했는지 체크해야하니까 길이는 dungeons길이만큼
dfs(dungeons);
return answer;
}
static void dfs(int[][] dungeons)
if(static_count>answer){
answer=static_count;}
for(int i=0; i<dungeons.length; i++){
if(static_k>=dungeons[i][0] && !visited[i]){ //현재피로도가 어떤 던전의 최소필요피로도보다 크거나 같고 아직방문 하지 않았다면 탐색 가능
visited[i]=true; //탐색에 들어가면 방문체크 하고
static_k -= dungeons[i][1]; //던전에 진입했으니 피로도에서 소모피로도를 빼준다.
static_count +=1;//던전에 방문했으니 방문횟수 체크해준다.
dfs(dungeons);//다른 던전을 방문하기 위해 재귀호출
visited[i]=false; // 리턴되면 백트래킹.방문,피로도,방문횟수 다 원래값으로 돌려준다
static_k += dungeons[i][1];
static_count -=1;
}
}
}
-----------------------------------------------------------------------
ex.k=80(현재피로도), dungeons={{80,20},{50,40},{30,10}} 상태에서 dfs실행하면,
(static_k를 k로, static_count를 count로 표현하겠음)
먼저 for문 실행되고
1.i=0일 때 k는 80으로 던전[0][0](즉 80)보다 크거나 같고, visited[0]=true니까 if절 충족
visited[0]= true; k=60, count=1;인 상태에서 dfs재귀호출
//재귀호출 된 for문의 i는 j라 표현하겠다.
2.상단 if절에서 answer=1이 되고, for문 j=0(i=0인상태)에서 visited[0]=true니까 if절 충족안되고,
i=0,j=1로 넘어감. 이때 k=60으로 던전[1][0](즉 50)보다 크고 visited[1]=false니까 if절 충족
따라서, visited[1]=true; k=20; count=2인 상태에서 dfs재귀호출
3.상단 if절에서 answer=2가 되고, for문 l=0(i=0,j=1인상태)에서 0과1 방문처리되어 l=2일때
for문들어가나 k=20으로 던전[2][0](즉,30)보다 작아서 if절 충족x l=0,1,2 for문 다 돌았으니 재귀완료
4.i=0,j=1인 2번상태로 돌아와 visited[1]= false; k=60; count=1로 백트래킹.
그런다음 j=2가 되어 if절 충족하여 visited[2]=true k=50; count=2인 상태로 재귀호출
5.l=0(i=0,j=2)에 어차피 서visited[0]과[2]가 true기 때문에 l=1일 때 확인하면
k가 50으로 던전[1][0](50)보다 크거나 같고 visited[1]=false니까 if절 충족!
따라서 visited[1]=true; k=10; count=3;인 상태에서 재귀호출.
6.상단 if절에서 answer=3으로 갱신되고 0,1,2 모두 true로 for문 if절 충족하지 않고 반복을 다돌게 되면서
재귀 완료. 그러면 5번상태로 돌아와 [t,f,t], k=50, count=2로 돌아오고 그게 또 재귀 완료되어
4번 상태로 돌아감. [t,f,f] k=60, count=1로 백트래킹 되고 또 재귀 완료.
[f,f,f] k=80, count=0으로 완전 초기화가 되었고
7.가장 처음인 1번 상태로 돌아와 i=1일때 부터 다시 시작하는 거임.
8.즉, 1번~6번까지의 과정이 던전0,던전1,던전2를 탐색했으나 던전0과 1만 진입이 가능하였고
백트래킹되어 던전0,던전2,던전1순으로 탐색하여 3개모두 진입한 과정임.
그리고 7번에서부터 시작되는 또 재귀호춯은 던전1부터 진입하는 과정을 그리게 되는 것
그 과정은 아래와 같음
Class Solution{
static int answer; //마찬가지로 dfs메서드 안에서도 공유하기 위해
public int soulution(int k, int[][] dungeons){
visited= new boolean[dungeons]// 어떤 던전을 방문했는지 체크해야하니까 길이는 dungeons길이만큼
int count =0;
dfs(dungeons,k,visited,0);
return answer;
}
static void dfs(int[][] dungeons,int k,boolean[]visited, int count)
if(count>answer){
answer=count;}
for(int i=0; i<dungeons.length; i++){
if(static_k>=dungeons[i][0] && !visited[i]){ //현재피로도가 어떤 던전의 최소필요피로도보다 크거나 같고 아직방문 하지 않았다면 탐색 가능
visited[i]=true; //탐색에 들어가면 방문체크 하고
dfs(dungeons,k-dungeons[i][1],count+1);//다른 던전을 방문하기 위해 재귀호출
visited[i]=false;
}
}
-----------------------------
어차피 재귀가 완료되면 그 전 상태로 돌아오기 때문에 k값과 count 값을 처음부터 재귀함수의 매개변수로
동적으로 들고가면 재귀된 상태의 k값과 count값이 재귀 이전의 함수의 k와 count에 영향을 주지않기 때문에
따로 백트래킹 처리를 할 필요가 없는 것임!
public class 게임맵_최단거리2 {
static int[] dx ={-1,1,0,0};
static int[] dy ={0,0,-1,1};
--> dx,dy배열은 한 좌표의 상하좌우 이동을 나타내기 위한 배열.
예를 들어, (1,1)은 1행1열에 위치해있는데 앞,뒤 요소에 각각 dx[0],dy[0]을 더해주면 (0,1)로
0행 1열 즉 위로 한 칸 이동하는 개념이 된다. 마찬가지로 dx[2],dy[2]를 더해주면 (1,0)으로
1행 0열 즉 왼쪽으로 한 칸 이동하는 개념이 된다. 이런 방식으로 활용하기 위해 만든 배열이다.
public static void main(String[] args) {
int[][]maps ={{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,0},{0,0,0,0,1}};
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0,0}); //큐에 먼저 출발지점을 넣고
while(!q.isEmpty()){
int[] temp = q.poll();
if(temp[0]== maps.length-1 && temp[1] == maps[0].length-1){
break;
}
for(int i=0; i<4; i++){
int mx = temp[0]+dx[i];
int my = temp[1]+dy[i]; // 한 좌표에서 상하좌우 이동을 나타내고
if(mx>=0 && mx<maps.length && my>=0 && my<maps[0].length){
if(maps[mx][my]==1){
q.add(new int[]{mx,my});
maps[mx][my] = maps[temp[0]][temp[1]]+1;
}
--> 기존 좌표에서 상하좌우를 이동하는 좌표가 어찌됐든 맵에서 벗어나지 않아야하니까
0보다크고 가로 세로길이보다 작은 조건을 달아야하고 큐에 넣어야 할 요소는 즉
이동할 수 있는 경로는 현재 맵에서 값 1을 가지고 있으므로 map[mx][my]==1조건이 있어야한다.
그리고 큐에 넣었다는 것은 이동(탐색)했다는 뜻이고 그 지점의 값을 이전 값에서 +1을 해준다는 것은
그 지점까지가는 최단경로를 나타내는 것이다.
큐에 넣어 탐색하는 bfs자체가 최단경로로 이동하기 떄문
}
}
}
int result = maps[maps.length-1][maps[0].length-1];
if(result>1){
System.out.println(result);
} else{
System.out.println(-1);
}
}
}