swexpert : 미로1

🏆 문제정보

문제 : 1226. [S/W 문제해결 기본] 7일차 - 미로1

문제 난이도 : D4 (중하)

문제 유형 : DFS

📌 문제

출발 -> 2

도착점 ->3

벽 -> 1

지나갈 수 있는 곳 -> 0

 

2에서 출발해서 3으로 갈 때, 도착할 수 있는지 없는지 출력하라.

📌 생각

🔥 ||  - &&

if(isOut(movedX,movedY) || map[movedX][movedY] != 0){
    return ;
}

&& 가 아니라 || 여야 return 이 된다. 헷갈리지 말자!

🔥 방문처리

dfs의 경우, 상하좌우를 탐색하는데 , 방문처리를 해주지 않으면 무한루프를 돌 수 있다.

 

예를 들어

 

0 0 일 경우

-> 간 다음에 다시 <- 를 갈 수가 있다.

그래서 꼭 방문처리를 해주어야 한다.

private static void dfs(int movedX, int movedY) {
    if(movedX == end[0] && movedY == end[1]){
        flag=true;
    }

    if(isOut(movedX,movedY) || map[movedX][movedY] != 0){
        return ;
    }

    visited[movedX][movedY] = 1;

    for(int i=0;i<4;i++){
        int nx = movedX + dx[i];
        int ny = movedY + dy[i];

        if(!isOut(nx,ny) && visited[nx][ny] == 0) dfs(nx,ny);
    }
}

visited[movedX][movedY] = 1 <---- 방문처리

 

그 다음에는 방문처리가 안된 애들일 경우에만 방문

📌 코드

package src.swexpert.sol_210806.maze;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Locale;
import java.util.Scanner;

// 1226 미로 1
public class Maze {

    static int T=10;
    static int N=16;
    static int[][] map;

    // direction 경비원 , 달팽이 d= (d+1)%4
    // 특별한 방향이 없을 때

    static int[] dx= {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    static int[] start ;
    static int[] end;

    static int[][] visited;

    static boolean flag;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/swexpert/sol_210806/maze/input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int t=1;t<=T;t++){
            flag=false;
            int trash = Integer.parseInt(br.readLine());
            start = new int[2];
            end = new int[2];
            map = new int[N][N];
            visited = new int[N][N];

            // map 설정 . start end 설정
            for(int i=0;i<N;i++){
                String input = br.readLine();
                for(int j=0;j<N;j++){
                    int num = input.charAt(j) - '0';
                    if(num==2){
                        start[0] = i;
                        start[1] = j;
                    }else if(num==3){
                        end[0]=i;
                        end[1]=j;
                    }
                    map[i][j] = num;
                }
            }
            for(int i=0;i<4;i++){
                dfs(start[0]+dx[i],start[1]+dy[i]);
            }
            if(flag){
                System.out.println("#"+t+" " + 1);
            }else{
                System.out.println("#"+t+" " + 0);
            }
        }
    }

    static void print(int[][] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr.length;j++){
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    static boolean isOut(int nx,int ny){
        return nx<0 || nx>=N || ny<0 || ny>=N;
    }

    // or 설정 , 방문처리
    private static void dfs(int movedX, int movedY) {
        if(movedX == end[0] && movedY == end[1]){
            flag=true;
        }

        if(isOut(movedX,movedY) || map[movedX][movedY] != 0){
            return ;
        }

        visited[movedX][movedY] = 1;

        for(int i=0;i<4;i++){
            int nx = movedX + dx[i];
            int ny = movedY + dy[i];

            if(!isOut(nx,ny) && visited[nx][ny] == 0) dfs(nx,ny);
        }
    }
}