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

🔗 문제 링크: https://www.softeer.ai/practice/6246

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

📝 문제 요약

1️⃣ 주어진 격자가 존재하는데 격자의 내용은 0 또는 1로 구성되어 있다. 1은 격자 내에서 벽의 역할로 지나칠 수 없는 곳을 의미한다. 각 격자는 (1, 1)부터 시작이고, (행, 열) 형태의 좌표로 주어진다. 격자의 크기는 n x n이다.
2️⃣ 격자에서 방문해야 하는 m 개의 점이 주어진다. 점에서 첫 부분은 격자의 시작 지점이고, 마지막 부분은 도착 지점을 의미한다.
3️⃣ m개의 점을 주어진 순서대로 모두 방문해야 하고, 방문할 수 있는 경우의 수를 구해야 한다.

 

 

🔍  해결 과정

dfs를 통해서 시작 지점에서 끝지점으로 갈 때 주어진 m 개의 점을 순서대로 방문할 수 있는지 확인하는 방식으로 코드를 구현했습니다.

 

주의해야 할 점은 모든 m개의 점을 순서를 고려해야 한다는 점입니다.

m개의 점을 어떻게 순서대로 방문하는지 확인할 수 있도록 처리했는지 그 과정을 요약하면 다음과 같습니다.

1️⃣ 방문해야 하는 모든 점을 하나의 좌표 리스트 mustVisited 에 담아둔다. 입력 받은 좌표 순으로 담아둔다.
2️⃣ dfs를 통해 탐색하면서 mustVisited를 인덱싱을 통해서 계속 확인해준다.
3️⃣ 도착 지점에 왔을 때 mustVisited를 전부 돌아본 상태라면 가능한 경로이므로 개수를 카운트해준다.

 

 

---

✏️ 코드

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

class Pair {
    private final int x;
    private final int y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

public class Main {

    private static final int WALL = 1;

    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    private static int[][] board;
    private static boolean[][] visited;
    private static List<Pair> mustVisited = new ArrayList<>();
    private static int n, m;
    private static int answer = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][n];
        visited = new boolean[n][n];

        for (int i = 0; i < n; ++i) {
            board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        
        for (int i = 0; i < m; ++i) {
            st = new StringTokenizer(br.readLine());
            mustVisited.add(new Pair(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1));
        }

        int startX = mustVisited.get(0).getX();
        int startY = mustVisited.get(0).getY();
        int targetX = mustVisited.get(mustVisited.size() - 1).getX();
        int targetY = mustVisited.get(mustVisited.size() - 1).getY();

        dfs(startX, startY, targetX, targetY, 0);
        
        bw.write(Integer.toString(answer));
        bw.flush(); 
    }

    private static void dfs(int curX, int curY, 
                            final int targetX, final int targetY, int idx) {
        visited[curX][curY] = true;

        if (idx < mustVisited.size() && 
            curX == mustVisited.get(idx).getX() && curY == mustVisited.get(idx).getY()) {
            ++idx;
        }
        
        if (curX == targetX && curY == targetY) {
            
            if (idx == mustVisited.size()) {
                ++answer;
            }
            
            visited[curX][curY] = false;
            return;
        }

        for (int dir = 0; dir < 4; ++dir) {
            int nx = curX + dx[dir];
            int ny = curY + dy[dir];

            if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
                continue;
            }

            if (visited[nx][ny] || board[nx][ny] == WALL) {
                continue;
            }

            dfs(nx, ny, targetX, targetY, idx);
        }
        
        visited[curX][curY] = false;
    }
}