비트교육_단기과정
DFS 깊이 우선 탐색 Stack & Queue
- -
1. Stack_ver
package week_4; import java.util.Arrays; import java.util.Stack; public class DFS_LabyrinthSearch { public static void main(String[] args) { int cnt = 0; int[][] load = { { 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0 }, { 0, -1, -1, -1, 0, -1, -1, 0, -1, -1, -1, -1, 0, 0, 0, -1, }, { 0, -1, -1, -1, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, 0, -1 }, { 0, -1, 0, 0, 0, -1, -1, 0, -1, 0, -1, -1, -1, -1, 0, -1 }, { 0, -1, 0, -1, -1, -1, -1, 0, -1, 0, -1, -1, -1, -1, 0, -1 }, { 0, -1, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0 }, { 0, -1, 0, -1, 0, -1, -1, 0, -1, 0, -1, -1, 0, -1, -1, 0 }, { 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, 0 }, { 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0 }, { 0, -1, 0, -1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }, { 0, -1, 0, -1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, -1, 0, 0, 0, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, 0 }, { 0, -1, 0, -1, -1, -1, -1, 0, 0, 0, 0, -1, -1, -1, 0, 0 }, { -1, -1, 0, -1, -1, -1, -1, 0, -1, -1, 0, 0, -1, 0, -1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 0, -1, 0, -1, -1 }, { 0, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, 0, 0, 0, 0, 0 } }; int x = 0; // x좌표 int y = 0; // y좌표 int[] end = { 15, 15 }; // 종료 위치 Stack<int[]> stack = new Stack<>(); stack.push(new int[] { 0, 0 });// 우좌상하 do { int[] ps = stack.pop(); x = ps[1];// x좌표 0 y = ps[0];// y좌표 15 if (end[0] == y && end[1] == x) { System.out.println("정답 : " + y + " , " + x); load[y][x] = -2; break; } load[y][x] = -2;// 지나간 좌표 if (x > 0) { if (load[y][x - 1] >= 0) {// 왼쪽 타일값이 0일경우 =>>왼쪽 타일 검색 load[y][x - 1] = 2; stack.push(new int[] { y, x - 1 }); } } if (x < load[y].length - 1) {// 현재위치의 x좌표가 x축 끝 좌표보다 작고 if (load[y][x + 1] >= 0) {// 오른쪽의 타일값이 0보다 클 경우 =>>오른쪽 타일 검색 || 타일의값이 0이면 아직 안간 곳 || 조건을 크거나 같다 한 이유는 // 목표값이 100이기떄문이다 load[y][x + 1] = 2; stack.push(new int[] { y, x + 1 }); } } if (y > 0) { if (load[y - 1][x] >= 0) {// 위쪽 타일검색 load[y - 1][x] = 2; stack.push(new int[] { y - 1, x }); } } if (y < load.length - 1) { if (load[y + 1][x] >= 0) {// 아래쪽 타일검색 load[y + 1][x] = 2; stack.push(new int[] { y + 1, x }); } } if (stack.isEmpty()) { // 길을 다 돌때 까지 종료를 못찾은 경우 break; } } while (true); for (int i = 0; i < load.length; i++) { for (int j = 0; j < load[i].length; j++) { if (load[i][j] == 0) { System.out.print("□"); } else if (load[i][j] == -2) { if (i == 15 && j == 15) { System.out.print("X"); } else { System.out.print("@"); } } else if (load[i][j] == -1) { System.out.print("■"); } else if (load[i][j] == 2) { System.out.print("$"); } } System.out.println(); } while (!stack.isEmpty()) { System.out.println(Arrays.toString(stack.pop())); } } } | cs |
2. Queue_ver
package week_4; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class DFS_LabyrinthSearch { public static void main(String[] args) { int[][] load = { { 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0 }, { 0, -1, -1, -1, 0, -1, -1, 0, -1, -1, -1, -1, 0, 0, 0, -1, }, { 0, -1, -1, -1, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, 0, -1 }, { 0, -1, 0, 0, 0, -1, -1, 0, -1, 0, -1, -1, -1, -1, 0, -1 }, { 0, -1, 0, -1, -1, -1, -1, 0, -1, 0, -1, -1, -1, -1, 0, -1 }, { 0, -1, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0 }, { 0, -1, 0, -1, 0, -1, -1, 0, -1, 0, -1, -1, 0, -1, -1, 0 }, { 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, 0 }, { 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0 }, { 0, -1, 0, -1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }, { 0, -1, 0, -1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, -1, 0, 0, 0, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, 0 }, { 0, -1, 0, -1, -1, -1, -1, 0, 0, 0, 0, -1, -1, -1, 0, 0 }, { -1, -1, 0, -1, -1, -1, -1, 0, -1, -1, 0, 0, -1, 0, -1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 0, -1, 0, -1, -1 }, { 0, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, 0, 0, 0, 0, 0 } }; int x = 0; // x좌표 int y = 0; // y좌표 int[] end = { 15, 15 }; // 종료 위치 Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[] { 0, 0 });// 우좌상하 do { int[] ps = changeQueue(queue); x = ps[1];// x좌표 0 y = ps[0];// y좌표 15 if (end[0] == y && end[1] == x) { System.out.println("정답 : " + y + " , " + x); load[y][x] = -2; break; } load[y][x] = -2;// 지나간 좌표 if (x > 0) { if (load[y][x - 1] >= 0) {// 왼쪽 타일값이 0일경우 =>>왼쪽 타일 검색 load[y][x - 1] = 2; queue.offer(new int[] { y, x - 1 }); } } if (x < load[y].length - 1) {// 현재위치의 x좌표가 x축 끝 좌표보다 작고 if (load[y][x + 1] >= 0) {// 오른쪽의 타일값이 0보다 클 경우 =>>오른쪽 타일 검색 || 타일의값이 0이면 아직 안간 곳 || 조건을 크거나 같다 한 이유는 // 목표값이 100이기떄문이다 load[y][x + 1] = 2; queue.offer(new int[] { y, x + 1 }); } } if (y > 0) { if (load[y - 1][x] >= 0) {// 위쪽 타일검색 load[y - 1][x] = 2; queue.offer(new int[] { y - 1, x }); } } if (y < load.length - 1) { if (load[y + 1][x] >= 0) {// 아래쪽 타일검색 load[y + 1][x] = 2; queue.offer(new int[] { y + 1, x }); } } if (queue.isEmpty()) { // 길을 다 돌때 까지 종료를 못찾은 경우 break; } } while (true); for (int i = 0; i < load.length; i++) { for (int j = 0; j < load[i].length; j++) { if (load[i][j] == 0) { System.out.print("□"); } else if (load[i][j] == -2) { if (i == 15 && j == 15) { System.out.print("X"); } else { System.out.print("@"); } } else if (load[i][j] == -1) { System.out.print("■"); } else if (load[i][j] == 2) { System.out.print("$"); } } System.out.println(); } while (!queue.isEmpty()) { System.out.println(Arrays.toString(queue.poll())); } } public static int[] changeQueue(Queue<int[]> queue) { // 큐의 마지막 값 전까지 앞의 모든 값을 다시 자기자신에게 offer함으로써 가장 늦게 넣은 갑을 poll해주는 메서드 int cnt = 0; int size = queue.size(); int[] temp = null; while (cnt != size) { temp = queue.poll(); if (++cnt == size) { return temp; } else queue.offer(temp); } return temp; } } | cs |
'비트교육_단기과정' 카테고리의 다른 글
정렬알고리즘(버블, 선택, 삽입, 쉘 정렬) (0) | 2022.07.18 |
---|---|
BFS 너비 우선 탐색 Stack & Queue (0) | 2022.07.15 |
후위표기법 stack을 사용하여 수식계산 (0) | 2022.07.14 |
이진검색 재귀함수 : 마기창 (0) | 2022.07.13 |
팩토리얼을 재귀함수로 구현 (0) | 2022.07.13 |
Contents
소중한 공감 감사합니다