[Softeer] LV.3 [HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기 (JAVA)

문제

https://softeer.ai/app/assessment/index.html?xid=102826&xsrfToken=AQ1kWx3e3jDdaW7IokwfJf6ATIDezOXG&testType=practice

접근 방식

DFS방식으로 각 노드를 순차적으로 방문할 수 있게 구현

문제를 보자마자 최단 거리를 구하는 게 아닌, 경로의 갯수를 구하는 문제였기 때문에 DFS로 문제를 풀어야겠다고 생각했다.

노드를 여러번 방문해야하며, 이전에 지나간 경로는 지나갈 수 없기 때문에 각 노드까지 DFS로 경로를 탐색하고 도착하면 다음 노드로 향해야한다. 그래서 나는 아래와 같은 재귀가 필요하다고 생각했다. 내가 생각한 재귀 방식은 아래와 같다.

  public static void dfs (int index, int x, int y){
  		
        ... (생략)
        
        if(x == node[index+1].x && y == node[index+1].y){ // 도착점 도착했을 경우
            if(index+1 == m-1){ // 마지막 노드였다면, count 증가
                count++;
                return;
            }
            else{ // 아닐경우, 다음노드까지 가기 위한 경로 탐색
                dfs(index+1,x,y);
            }
        }

DFS 구현 방식 중 먼저 시도한 방법은 더 익숙한 stack을 이용한 DFS 구현이었다.
하지만 stack을 이용하게 되면 재귀함수로 다음 노드의 경로를 구하고 다시 돌아올 때, 방문을 초기화 할 수가 없었다. 그래서 재귀함수로 dfs를 구현하면서 문제를 해결할 수 있었다.

정답코드

import java.io.*;
import java.util.*;

public class Main {
    static class Node{
        int x,y,v;
        Node(int x, int y, int v){
            this.x = x;
            this.y = y;
            this.v = v;
        }
    }
    static int [][] dist = {{-1,1,0,0},{0,0,-1,1}};

    static int n;
    static int m;
    static int [][] board;
    static Node [] node;
    static boolean [][] visited;
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String [] strs = br.readLine().split(" ");
        n = Integer.parseInt(strs[0]);
        m = Integer.parseInt(strs[1]);
        board = new int [n][n];
        node = new Node [m];
        visited = new boolean[n][n];
        count =0;
        
        for(int i=0;i<n;i++){
            strs = br.readLine().split(" ");
            for(int j=0; j<n;j++){
                board[i][j] = Integer.parseInt(strs[j]);
            }
        }
        
        for(int i=0;i<m;i++){
            strs = br.readLine().split(" ");
            int x = Integer.parseInt(strs[0])-1;
            int y = Integer.parseInt(strs[1])-1;
            node[i] = new Node(x,y,0); 
        }
        dfs(0,node[0].x, node[0].y);
        System.out.println(count);
    }

    public static void dfs (int index, int x, int y){
        visited[x][y] = true;
        if(x == node[index+1].x && y == node[index+1].y){
            if(index+1 == m-1){
                count++;
                return;
            }
            else{
                dfs(index+1,x,y);
            }
        }
        for(int i=0;i<4;i++){
            int nextX = x+ dist[0][i];
            int nextY = y+ dist[1][i];
            if(nextX<0||nextX>n-1||nextY<0||nextY>n-1) continue;
            if(visited[nextX][nextY]) continue;
            if(board[nextX][nextY]==1) continue;
            dfs(index,nextX,nextY);
            visited[nextX][nextY]= false;
        }
        
        return;
    }
}

이 문제를 풀면서 배운점은

dfs를 구현 할 때, Stack과 재귀함수의 차이

• 스택을 사용하는 경우: 탐색 과정에서의 제어가 필요한 경우 / 재귀 호출에 대한 깊이 제한이 있는 경우
• 재귀 함수를 사용하는 경우: 코드가 간결해야하는 경우 / 중첩하여 함수를 사용 하게 될 경우 / 방문 처리를 되돌려야 하는 경우