πŸ”₯[99클럽 μ½”ν…Œ μŠ€ν„°λ””] 35일차 TIL - κ²Œμž„ 맡 μ΅œλ‹¨κ±°λ¦¬

HOONSSACΒ·2024λ…„ 8μ›” 25일
1

99Club Coding Test Study

λͺ©λ‘ 보기
35/41
post-thumbnail

⏳문제

ROR κ²Œμž„μ€ 두 νŒ€μœΌλ‘œ λ‚˜λˆ„μ–΄μ„œ μ§„ν–‰ν•˜λ©°, μƒλŒ€ νŒ€ μ§„μ˜μ„ λ¨Όμ € νŒŒκ΄΄ν•˜λ©΄ μ΄κΈ°λŠ” κ²Œμž„μž…λ‹ˆλ‹€. λ”°λΌμ„œ, 각 νŒ€μ€ μƒλŒ€ νŒ€ μ§„μ˜μ— μ΅œλŒ€ν•œ 빨리 λ„μ°©ν•˜λŠ” 것이 μœ λ¦¬ν•©λ‹ˆλ‹€.

μ§€κΈˆλΆ€ν„° 당신은 ν•œ νŒ€μ˜ νŒ€μ›μ΄ λ˜μ–΄ κ²Œμž„μ„ μ§„ν–‰ν•˜λ €κ³  ν•©λ‹ˆλ‹€. λ‹€μŒμ€ 5 x 5 크기의 맡에, λ‹Ήμ‹ μ˜ 캐릭터가 (ν–‰: 1, μ—΄: 1) μœ„μΉ˜μ— 있고, μƒλŒ€ νŒ€ μ§„μ˜μ€ (ν–‰: 5, μ—΄: 5) μœ„μΉ˜μ— μžˆλŠ” 경우의 μ˜ˆμ‹œμž…λ‹ˆλ‹€.

μœ„ κ·Έλ¦Όμ—μ„œ 검은색 뢀뢄은 벽으둜 λ§‰ν˜€μžˆμ–΄ 갈 수 μ—†λŠ” 길이며, 흰색 뢀뢄은 갈 수 μžˆλŠ” κΈΈμž…λ‹ˆλ‹€. 캐릭터가 움직일 λ•ŒλŠ” 동, μ„œ, 남, 뢁 λ°©ν–₯으둜 ν•œ μΉΈμ”© μ΄λ™ν•˜λ©°, κ²Œμž„ 맡을 λ²—μ–΄λ‚œ 길은 갈 수 μ—†μŠ΅λ‹ˆλ‹€.
μ•„λž˜ μ˜ˆμ‹œλŠ” 캐릭터가 μƒλŒ€ νŒ€ μ§„μ˜μœΌλ‘œ κ°€λŠ” 두 가지 방법을 λ‚˜νƒ€λ‚΄κ³  μžˆμŠ΅λ‹ˆλ‹€.

  • 첫 번째 방법은 11개의 칸을 μ§€λ‚˜μ„œ μƒλŒ€ νŒ€ μ§„μ˜μ— λ„μ°©ν–ˆμŠ΅λ‹ˆλ‹€.
  • 두 번째 방법은 15개의 칸을 μ§€λ‚˜μ„œ μƒλŒ€νŒ€ μ§„μ˜μ— λ„μ°©ν–ˆμŠ΅λ‹ˆλ‹€.

μœ„ μ˜ˆμ‹œμ—μ„œλŠ” 첫 번째 방법보닀 더 λΉ λ₯΄κ²Œ μƒλŒ€νŒ€ μ§„μ˜μ— λ„μ°©ν•˜λŠ” 방법은 μ—†μœΌλ―€λ‘œ, 이 방법이 μƒλŒ€ νŒ€ μ§„μ˜μœΌλ‘œ κ°€λŠ” κ°€μž₯ λΉ λ₯Έ λ°©λ²•μž…λ‹ˆλ‹€.

λ§Œμ•½, μƒλŒ€ νŒ€μ΄ μžμ‹ μ˜ νŒ€ μ§„μ˜ μ£Όμœ„μ— 벽을 μ„Έμ›Œλ‘μ—ˆλ‹€λ©΄ μƒλŒ€ νŒ€ μ§„μ˜μ— λ„μ°©ν•˜μ§€ λͺ»ν•  μˆ˜λ„ μžˆμŠ΅λ‹ˆλ‹€. 예λ₯Ό λ“€μ–΄, λ‹€μŒκ³Ό 같은 κ²½μš°μ— λ‹Ήμ‹ μ˜ μΊλ¦­ν„°λŠ” μƒλŒ€ νŒ€ μ§„μ˜μ— 도착할 수 μ—†μŠ΅λ‹ˆλ‹€.

κ²Œμž„ 맡의 μƒνƒœ mapsκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, 캐릭터가 μƒλŒ€ νŒ€ μ§„μ˜μ— λ„μ°©ν•˜κΈ° μœ„ν•΄μ„œ μ§€λ‚˜κ°€μ•Ό ν•˜λŠ” 칸의 개수의 μ΅œμ†Ÿκ°’μ„ return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄μ£Όμ„Έμš”. 단, μƒλŒ€ νŒ€ μ§„μ˜μ— 도착할 수 없을 λ•ŒλŠ” -1을 return ν•΄μ£Όμ„Έμš”.

πŸš¨μ œν•œ 사항

  • mapsλŠ” n x m 크기의 κ²Œμž„ 맡의 μƒνƒœκ°€ λ“€μ–΄μžˆλŠ” 2차원 λ°°μ—΄λ‘œ, nκ³Ό m은 각각 1 이상 100 μ΄ν•˜μ˜ μžμ—°μˆ˜μž…λ‹ˆλ‹€.

  • nκ³Ό m은 μ„œλ‘œ 같을 μˆ˜λ„, λ‹€λ₯Ό μˆ˜λ„ μžˆμ§€λ§Œ, nκ³Ό m이 λͺ¨λ‘ 1인 κ²½μš°λŠ” μž…λ ₯으둜 주어지지 μ•ŠμŠ΅λ‹ˆλ‹€.

  • mapsλŠ” 0κ³Ό 1둜만 이루어져 있으며, 0은 벽이 μžˆλŠ” 자리, 1은 벽이 μ—†λŠ” 자리λ₯Ό λ‚˜νƒ€λƒ…λ‹ˆλ‹€.

  • μ²˜μŒμ— μΊλ¦­ν„°λŠ” κ²Œμž„ 맡의 쒌츑 상단인 (1, 1) μœ„μΉ˜μ— 있으며, μƒλŒ€λ°© μ§„μ˜μ€ κ²Œμž„ 맡의 우츑 ν•˜λ‹¨μΈ (n, m) μœ„μΉ˜μ— μžˆμŠ΅λ‹ˆλ‹€.

πŸ“„μž…μΆœλ ₯ 예

mapsanswer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]-1

μž…μΆœλ ₯ 예 #1

주어진 λ°μ΄ν„°λŠ” λ‹€μŒκ³Ό κ°™μŠ΅λ‹ˆλ‹€.

캐릭터가 적 νŒ€μ˜ μ§„μ˜κΉŒμ§€ μ΄λ™ν•˜λŠ” κ°€μž₯ λΉ λ₯Έ 길은 λ‹€μŒ κ·Έλ¦Όκ³Ό κ°™μŠ΅λ‹ˆλ‹€.

λ”°λΌμ„œ 총 11칸을 캐릭터가 μ§€λ‚˜κ°”μœΌλ―€λ‘œ 11을 return ν•˜λ©΄ λ©λ‹ˆλ‹€.

μž…μΆœλ ₯ 예 #2

문제의 μ˜ˆμ‹œμ™€ κ°™μœΌλ©°, μƒλŒ€ νŒ€ μ§„μ˜μ— 도달할 방법이 μ—†μŠ΅λ‹ˆλ‹€. λ”°λΌμ„œ -1을 return ν•©λ‹ˆλ‹€.


βœοΈν’€μ΄

이 λ¬Έμ œλŠ” 주어진 2차원 λ°°μ—΄μ—μ„œ μΆœλ°œμ λΆ€ν„° λ„μ°©μ κΉŒμ§€μ˜ μ΅œλ‹¨ 경둜λ₯Ό μ°ΎλŠ” λ¬Έμ œμ΄λ‹€. λ”°λΌμ„œ μ΅œλ‹¨ 경둜 μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ 많이 μ‚¬μš©ν•˜λŠ” BFS(λ„ˆλΉ„ μš°μ„  탐색)을 μ‚¬μš©ν•΄ ν’€μ–΄λ³΄μ•˜λ‹€.

ꡬ해야 ν•˜λŠ” 것은 λ„μ°©μ κΉŒμ§€ κ°€λŠ” μ΅œλ‹¨ 경둜의 거리이기 λ•Œλ¬Έμ—,
큐에 ν˜„μž¬ μ’Œν‘œλ₯Ό μ €μž₯ν•  λ•Œ ν˜„μž¬κΉŒμ§€μ˜ 거리 정보λ₯Ό ν•¨κ»˜ μ €μž₯ν•΄μ•Ό ν•˜κ³ , μœ„μΉ˜λ₯Ό 이동할 λ•Œ 거리 정보λ₯Ό μ—…λ°μ΄νŠΈ ν•΄μ£Όμ–΄μ•Ό ν•œλ‹€λŠ” 점이 μ€‘μš”ν•˜λ‹€.

πŸ‘Ύμ΅œμ’… μ½”λ“œ

import java.util.*;

class Solution {
    static boolean[][] visited; // λ°©λ¬Έ μ—¬λΆ€
    static int nLen; // κ°€λ‘œ 길이
    static int mLen; // μ„Έλ‘œ 길이
    static int[][] step = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // μƒν•˜μ’Œμš° 이동

    public static int solution(int[][] maps) {
        nLen = maps[0].length; // κ°€λ‘œ 길이 (μ—΄)
        mLen = maps.length; // μ„Έλ‘œ 길이 (ν–‰)
        visited = new boolean[mLen][nLen]; // λ°©λ¬Έ μ—¬λΆ€ λ°°μ—΄ 생성

        return bfs(0, 0, maps);
    }
    
    public static int bfs(int x, int y, int[][] maps) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x, y, 1}); // μ‹œμž‘μ κ³Ό 거리 1 μ €μž₯
        visited[x][y] = true; // μ‹œμž‘μ  λ°©λ¬Έ μ—¬λΆ€ μ €μž₯

        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // ν˜„μž¬ μœ„μΉ˜
            int curX = current[0];
            int curY = current[1];
            int distance = current[2];

            // 도착점에 λ„λ‹¬ν•œ 경우
            if (curX == mLen - 1 && curY == nLen - 1) {
                return distance; // μ΅œλ‹¨ 거리 λ°˜ν™˜
            }

            for (int i = 0; i < 4; i++) {
                int newX = curX + step[i][0];
                int newY = curY + step[i][1];

                // μœ νš¨ν•œ μœ„μΉ˜μΈμ§€ 확인
                if (newX >= 0 && newX < mLen && newY >= 0 && newY < nLen) {
                    // 이동할 수 μžˆλŠ” μœ„μΉ˜μ΄λ©΄μ„œ 아직 λ°©λ¬Έν•˜μ§€ μ•Šμ€ 경우
                    if (maps[newX][newY] == 1 && !visited[newX][newY]) {
                        visited[newX][newY] = true; // 방문 처리
                        queue.offer(new int[] {newX, newY, distance + 1}); // 거리 μ—…λ°μ΄νŠΈ
                    }
                }
            }
        }
        return -1; // λͺ©μ μ§€μ— 도착할 수 μ—†λŠ” 경우

    }
}

πŸ‘Ύμ½”λ“œ μ„€λͺ…

  1. 맡의 κ°€λ‘œ 길이, μ„Έλ‘œ 길이λ₯Ό κ΅¬ν•˜κ³  ν•΄λ‹Ή 크기만큼의 2차원 λ°°μ—΄ visitedλ₯Ό 생성해 μ€€λ‹€. 이 배열은 maps와 같은 크기둜, λ°©λ¬Έ μ—¬λΆ€λ₯Ό μ €μž₯ν•˜λŠ” 역할을 ν•œλ‹€.

  2. λ„ˆλΉ„ μš°μ„  탐색(BFS)을 μœ„ν•œ 큐λ₯Ό μƒμ„±ν•˜κ³ , μ‹œμž‘μ  (0, 0)κ³Ό ν˜„μž¬κΉŒμ§€μ˜ 거리 1을 큐에 μ €μž₯ν•œλ‹€. 그리고 μ‹œμž‘μ  (0, 0)에 λŒ€ν•œ λ°©λ¬Έ 여뢀도 μ €μž₯ν•œλ‹€.

  3. νμ—μ„œ pollν•œ ν˜„μž¬ μœ„μΉ˜ 정보λ₯Ό 확인해 도착점에 λ„λ‹¬ν•œ 경우, 즉 (n, m)의 μœ„μΉ˜μ™€ μΌμΉ˜ν•˜λŠ” 경우 μ§€κΈˆκΉŒμ§€μ˜ 총 거리 distanceλ₯Ό λ°˜ν™˜ν•΄ μ€€λ‹€.

  4. ν˜„μž¬ μœ„μΉ˜κ°€ 도착점이 μ•„λ‹ˆλΌλ©΄, 계속 이동을 ν•΄μ•Ό ν•˜λ―€λ‘œ, ν˜„μž¬ μœ„μΉ˜λ₯Ό κΈ°μ€€μœΌλ‘œ μƒν•˜μ’Œμš° μœ„μΉ˜λ₯Ό ν™•μΈν•œλ‹€.

  5. μƒν•˜μ’Œμš° μœ„μΉ˜λ“€ 쀑 맡의 λ²”μœ„ λ‚΄μ•  μžˆμœΌλ©΄μ„œ 아직 λ°©λ¬Έν•˜μ§€ μ•Šμ€ 경우, ν•΄λ‹Ή μœ„μΉ˜λ₯Ό λ°©λ¬Έν•˜κ³  큐에 μ €μž₯ν•œλ‹€. 이 λ•Œ, ν•œ μΉΈ μ΄λ™ν–ˆκΈ° λ•Œλ¬Έμ— 거리 distanceμ—λŠ” 1을 λ”ν•΄μ„œ μ €μž₯ν•œλ‹€.

  6. 큐가 빌 λ•ŒκΉŒμ§€ 3~5번 과정을 λ°˜λ³΅ν•œλ‹€.


πŸ”—λ¬Έμ œ 링크
πŸ’»Repository

profile
ν›ˆμ‹Ήμ˜ κ°œλ°œμ—¬ν–‰

0개의 λŒ“κΈ€