https://school.programmers.co.kr/learn/courses/30/lessons/159993
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
소감
DFS 완전깊이탐색
연습하려고 골랐지만...
최단 거리를 구할때는 BFS가 적합하다고 한다
최소 시간을 계산하기 위해서는
1) 출발 지점에서 레버까지
2) 레버에서 출구까지의
최단 경로를 찾아야 합니다.
아 머리 아파.... 예민해지는 중..
DFS 수도 코드
import java.util.Arrays;
public class 미로탈출 {
//https://school.programmers.co.kr/learn/courses/30/lessons/42860
public static void main(String[] args) {
미로탈출.Solution solution = new 미로탈출.Solution();
String[] maps = {"SOOOL", "XXXXO", "OOOOO", "OXXXX", "OOOOE"};
int result = solution.solution(maps);
System.out.println("result>>>" + result);//16
}
static class Solution {
public int solution(String[] maps) {
int leng = maps.length;
String[][] arrTwo = new String[leng][leng];
int totalMovingCount = -1;
// 2차원 배열 만들기
for (int i = 0; i < leng; i++) {
arrTwo[i] = maps[i].split("");
}
// DFS 시작
for (int i = 0; i < leng; i++) {
for (int j = 0; j < leng; j++) {
//Start 지점 찾기
int[] StringPont = findStartPoint(i, j, arrTwo);
if (StringPont != null) {
//Start에서 DFS 시작, start지점 전달
DFS(StringPont[0], StringPont[1], arrTwo, totalMovingCount);
}
}
}
return totalMovingCount;
}
private int[] findStartPoint(int x, int y, String[][] twoArrays) {
if ("S".equals(twoArrays[x][y])) {
return new int[] {x, y};
} else {
return null;
}
}
private void DFS(int x, int y, String[][] twoArrays, int totalMovingCount) {
if (twoArrays[x][y].equals("X")) {//벽 못지나감
return;
}
if (twoArrays[x][y].equals("S")) {// 시작지점 아무것도 안함
// return;
}
if (twoArrays[x][y].equals("O") || twoArrays[x][y].equals("L")) {//통과, 카운트 증가
totalMovingCount++;
// return;
}
if (twoArrays[x][y].equals("E")) {// 종료
totalMovingCount++;
return;
}
int leng = twoArrays.length;
if (y >= 1 && x > 0 && y <= leng - 1 && x < leng) {
DFS(x, y - 1, twoArrays, totalMovingCount);
}
if (y >= -1 && x >= 0 && y < leng - 1 && x < leng) {
DFS(x, y + 1, twoArrays, totalMovingCount);
}
if (y > 0 && x >= 1 && y < leng && x <= leng) {
DFS(x - 1, y, twoArrays, totalMovingCount);
}
if (y > 0 && x >= -1 && y < leng && x < leng - 1) {
DFS(x + 1, y, twoArrays, totalMovingCount);
}
}
}//class end
}
더보기
현재 코드에서 몇 가지 문제가 있습니다. 주요 문제점은 다음과 같습니다:
- totalMovingCount 값의 전달 방식:
- totalMovingCount는 기본 타입 int로 전달되기 때문에, Java에서 값을 전달할 때 "값에 의한 전달"이 됩니다. 즉, 재귀 호출을 통해 값이 변경되더라도 원래 호출자에게는 반영되지 않습니다. 이 때문에 이동 횟수가 올바르게 누적되지 않습니다.
- DFS 탐색 로직의 문제:
- 탐색이 끝난 후 되돌아가는 로직(백트래킹)이나, 이미 방문한 지점을 체크하는 로직이 없습니다. 이로 인해 잘못된 경로로 들어가거나 무한 루프에 빠질 가능성이 있습니다.
- 지도 배열의 경계 체크:
- DFS 함수에서 경계 조건이 잘못 설정되어 있습니다. 예를 들어, (y >= 1 && x > 0 && y <= leng - 1 && x < leng)와 같은 조건들이 있는데, 이 부분이 올바르게 경계 체크를 하지 못하고 있습니다.
- StringPont 변수명:
- 변수명 StringPont는 StringPoint의 오타인 것으로 보입니다.
수정 제안:
- totalMovingCount를 전역 변수로 설정하거나, 객체를 통해 전달하여 재귀 호출 내에서 값을 유지하게 만듭니다.
- 방문 여부를 확인하는 2차원 배열을 추가하여 이미 방문한 곳을 다시 방문하지 않도록 합니다.
- DFS 탐색에서 배열의 경계 체크를 올바르게 설정합니다.
DFS 해결 코드
public class 미로탈출2 {
public static void main(String[] args) {
미로탈출2.Solution solution = new 미로탈출2.Solution();
String[] maps = {"SOOOL", "XXXXO", "OOOOO", "OXXXX", "OOOOE"};
int result = solution.solution(maps);
System.out.println("result>>>" + result); // 16
}
static class Solution {
// 공통 상수 처리
final static Integer ZERO = 0;
final static Integer NO_EXIT = -1;
private int totalMovingCount = ZERO; // 값에 의한 전달로 인해 공통 변수로 변경
// 추가) 중복 방문 체크 용
private boolean[][] visited;//초기값은 false
public int solution(String[] maps) {
int leng = maps.length;
String[][] arrTwo = new String[leng][];
visited = new boolean[leng][leng];
// 2차원 배열 만들기
for (int i = 0; i < leng; i++) {
arrTwo[i] = maps[i].split("");
}
// DFS 시작
for (int i = 0; i < leng; i++) {
for (int j = 0; j < arrTwo[i].length; j++) {
// Start 지점 찾기
int[] startPoint = findStartPoint(i, j, arrTwo);
if (startPoint != null) {
DFS(startPoint[0], startPoint[1], arrTwo, ZERO);// 값에의한 전달로 인해 totalMovingCount 변수 제거
}
}
}
return (totalMovingCount == ZERO) ? NO_EXIT : totalMovingCount;
}
private int[] findStartPoint(int x, int y, String[][] twoArrays) {
if ("S".equals(twoArrays[x][y])) {
return new int[] {x, y};
} else {
return null;
}
}
private void DFS(int x, int y, String[][] twoArrays, int currentCount) {
if (x < ZERO || y < ZERO || x >= twoArrays.length || y >= twoArrays[0].length) {
return; // 수정) 경계 체크
}
if (twoArrays[x][y].equals("X") || visited[x][y]) {
return; // 벽이거나 이미 방문한 경우
}
if (twoArrays[x][y].equals("E")) { // 출구를 찾은 경우
totalMovingCount = Math.max(totalMovingCount, currentCount);
return;// 게임 끝
}
visited[x][y] = true; // 현재 위치를 방문했다고 표시
// 상하좌우로 DFS 탐색
DFS(x - 1, y, twoArrays, currentCount + 1);
DFS(x + 1, y, twoArrays, currentCount + 1);
DFS(x, y - 1, twoArrays, currentCount + 1);
DFS(x, y + 1, twoArrays, currentCount + 1);
visited[x][y] = false; // 백트래킹을 위해 방문 표시를 해제
}
}// class end
}
BFS 해결 코드
1. directions 사용
2. 이중 배열 안 만듦
maps[i].charAt(j) == 'S'
3. 출발점에서 레버까지의 최단 거리 + 레버에서 출구까지의 최단 거리
4. 함수
int bfs(String[] maps, Point start, Point end, int rows, int cols)
5. 방문체크는 꼭 들어간다
6. BFS: Queue 사용
7. end에 도착하면 distance 리턴
8. 로직
if (
nx >= 0
&& nx < rows
&& ny >= 0
&& ny < cols
&& maps[nx].charAt(ny) != 'X'// 벽이 아닐 때
&& !visited[nx][ny]//이미 방문 중이 아닐 때
)
{
visited[nx][ny] = true;//방문중으로 체크
queue.add(new Point(nx, ny));// 큐에 넣는다
}
import java.util.LinkedList;
import java.util.Queue;
public class 미로탈출3 {
public static void main(String[] args) {
미로탈출3.Solution solution = new 미로탈출3.Solution();
String[] maps = {"SOOOL", "XXXXO", "OOOOO", "OXXXX", "OOOOE"};
int result = solution.solution(maps);
System.out.println("result >>> " + result); // 16
}
static class Solution {
private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우 이동
public int solution(String[] maps) {
int rows = maps.length;
int cols = maps[0].length();
Point start = null, lever = null, exit = null;
// 출발점(S), 레버(L), 출구(E)의 위치를 찾기
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 이중 배열 만들지도 않네, 포인트만 찾는 군
if (maps[i].charAt(j) == 'S') {
start = new Point(i, j);
}
if (maps[i].charAt(j) == 'L') {
lever = new Point(i, j);
}
if (maps[i].charAt(j) == 'E') {
exit = new Point(i, j);
}
}
}
// 출발점에서 레버까지의 최단 거리
int startToLever = bfs(maps, start, lever, rows, cols);
// 레버에서 출구까지의 최단 거리
int leverToExit = bfs(maps, lever, exit, rows, cols);
// 만약 하나라도 도달할 수 없다면 -1 반환
if (startToLever == -1 || leverToExit == -1) {
return -1;
}
return startToLever + leverToExit;
}
private int bfs(String[] maps, Point start, Point end, int rows, int cols) {
// 방문체크는 꼭 들어간다
boolean[][] visited = new boolean[rows][cols];
// BFS: Queue 사용
Queue<Point> queue = new LinkedList<>();
queue.add(start);
visited[start.x][start.y] = true;
int distance = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Point current = queue.poll();//큐에서 꺼낸다
if (current.x == end.x && current.y == end.y) {
return distance;
}// end에 도착하면 distance 리턴
// distance 늘리는 로직
for (int[] direction : directions) {
int nx = current.x + direction[0];
int ny = current.y + direction[1];
if (
nx >= 0
&& nx < rows
&& ny >= 0
&& ny < cols
&& maps[nx].charAt(ny) != 'X'// 벽이 아닐 때
&& !visited[nx][ny]//이미 방문 중이 아닐 때
)
{
visited[nx][ny] = true;//방문중으로 체크
queue.add(new Point(nx, ny));// 큐에 넣는다
}
}
}
distance++;
}
return -1; // 도달할 수 없는 경우
}
static class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}// class end
}
