๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 33์ผ์ฐจ TIL - ๋ฆฌ์ฝ”์ณ‡ ๋กœ๋ด‡

HOONSSACยท2024๋…„ 8์›” 24์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
33/41
post-thumbnail

โณ๋ฌธ์ œ

๋ฆฌ์ฝ”์ณ‡ ๋กœ๋ด‡์ด๋ผ๋Š” ๋ณด๋“œ๊ฒŒ์ž„์ด ์žˆ์Šต๋‹ˆ๋‹ค.

์ด ๋ณด๋“œ๊ฒŒ์ž„์€ ๊ฒฉ์ž๋ชจ์–‘ ๊ฒŒ์ž„ํŒ ์œ„์—์„œ ๋ง์„ ์›€์ง์ด๋Š” ๊ฒŒ์ž„์œผ๋กœ, ์‹œ์ž‘ ์œ„์น˜์—์„œ ๋ชฉํ‘œ ์œ„์น˜๊นŒ์ง€ ์ตœ์†Œ ๋ช‡ ๋ฒˆ๋งŒ์— ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๋งํ•˜๋Š” ๊ฒŒ์ž„์ž…๋‹ˆ๋‹ค.

์ด ๊ฒŒ์ž„์—์„œ ๋ง์˜ ์›€์ง์ž„์€ ์ƒ, ํ•˜, ์ขŒ, ์šฐ 4๋ฐฉํ–ฅ ์ค‘ ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•ด์„œ ๊ฒŒ์ž„ํŒ ์œ„์˜ ์žฅ์• ๋ฌผ์ด๋‚˜ ๋งจ ๋์— ๋ถ€๋”ชํž ๋•Œ๊นŒ์ง€ ๋ฏธ๋„๋Ÿฌ์ ธ ์ด๋™ํ•˜๋Š” ๊ฒƒ์„ ํ•œ ๋ฒˆ์˜ ์ด๋™์œผ๋กœ ์นฉ๋‹ˆ๋‹ค.

๋‹ค์Œ์€ ๋ณด๋“œ๊ฒŒ์ž„ํŒ์„ ๋‚˜ํƒ€๋‚ธ ์˜ˆ์‹œ์ž…๋‹ˆ๋‹ค.

...D..R
.D.G...
....D.D
D....D.
..D....

์—ฌ๊ธฐ์„œ .์€ ๋นˆ ๊ณต๊ฐ„์„, R์€ ๋กœ๋ด‡์˜ ์ฒ˜์Œ ์œ„์น˜๋ฅผ, D๋Š” ์žฅ์• ๋ฌผ์˜ ์œ„์น˜๋ฅผ, G๋Š” ๋ชฉํ‘œ์ง€์ ์„ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
์œ„ ์˜ˆ์‹œ์—์„œ๋Š” R ์œ„์น˜์—์„œ ์•„๋ž˜, ์™ผ์ชฝ, ์œ„, ์™ผ์ชฝ, ์•„๋ž˜, ์˜ค๋ฅธ์ชฝ, ์œ„ ์ˆœ์„œ๋กœ ์›€์ง์ด๋ฉด 7๋ฒˆ ๋งŒ์— G ์œ„์น˜์— ๋ฉˆ์ถฐ ์„ค ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ด๊ฒƒ์ด ์ตœ์†Œ ์›€์ง์ž„ ์ค‘ ํ•˜๋‚˜์ž…๋‹ˆ๋‹ค.

๊ฒŒ์ž„ํŒ์˜ ์ƒํƒœ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฌธ์ž์—ด ๋ฐฐ์—ด board๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋ง์ด ๋ชฉํ‘œ์œ„์น˜์— ๋„๋‹ฌํ•˜๋Š”๋ฐ ์ตœ์†Œ ๋ช‡ ๋ฒˆ ์ด๋™ํ•ด์•ผ ํ•˜๋Š”์ง€ return ํ•˜๋Š” solutionํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•˜์„ธ์š”. ๋งŒ์•ฝ ๋ชฉํ‘œ์œ„์น˜์— ๋„๋‹ฌํ•  ์ˆ˜ ์—†๋‹ค๋ฉด -1์„ return ํ•ด์ฃผ์„ธ์š”.

๐Ÿšจ์ œํ•œ ์‚ฌํ•ญ

  • 3 โ‰ค board์˜ ๊ธธ์ด โ‰ค 100
  • 3 โ‰ค board์˜ ์›์†Œ์˜ ๊ธธ์ด โ‰ค 100
  • board์˜ ์›์†Œ์˜ ๊ธธ์ด๋Š” ๋ชจ๋‘ ๋™์ผํ•ฉ๋‹ˆ๋‹ค.
  • ๋ฌธ์ž์—ด์€ ".", "D", "R", "G"๋กœ๋งŒ ๊ตฌ์„ฑ๋˜์–ด ์žˆ์œผ๋ฉฐ ๊ฐ๊ฐ ๋นˆ ๊ณต๊ฐ„, ์žฅ์• ๋ฌผ, ๋กœ๋ด‡์˜ ์ฒ˜์Œ ์œ„์น˜, ๋ชฉํ‘œ ์ง€์ ์„ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
  • "R"๊ณผ "G"๋Š” ํ•œ ๋ฒˆ์”ฉ ๋“ฑ์žฅํ•ฉ๋‹ˆ๋‹ค.

๐Ÿ“„์ž…์ถœ๋ ฅ ์˜ˆ

boardresult
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]7
[".D.R", "....", ".G..", "...D"]-1

์ž…์ถœ๋ ฅ ์˜ˆ #1

  • ๋ฌธ์ œ ์„ค๋ช…์˜ ์˜ˆ์‹œ์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

.D.R
....
.G..
...D
  • "R" ์œ„์น˜์— ์žˆ๋Š” ๋ง์„ ์–ด๋–ป๊ฒŒ ์›€์ง์—ฌ๋„ "G" ์— ๋„๋‹ฌ์‹œํ‚ฌ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ -1์„ return ํ•ฉ๋‹ˆ๋‹ค.

โœ๏ธํ’€์ด

์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ์•„์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ด๊ธฐ ๋•Œ๋ฌธ์—, BFS๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜์˜€๋‹ค.

์ƒํ•˜์ขŒ์šฐ๋ฅผ ์‚ดํ”ผ๊ธฐ ์œ„ํ•ด ์ด์ „ ๋ฌธ์ œ๋“ค์—์„œ ๊ตฌํ˜„ํ–ˆ๋˜ ๊ฒƒ๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ 2์ฐจ์› ๋ฐฐ์—ด์— ์ด๋™ ์ •๋ณด๋ฅผ ์ €์žฅํ•ด ์‚ฌ์šฉํ•˜์˜€๋‹ค.
์ด ๋ฌธ์ œ์—์„œ ์ค‘์š”ํ•œ ์ ์€ ์ด๋™ ์ค‘ ์žฅ์• ๋ฌผ์„ ๋งŒ๋‚ฌ์„ ๋•Œ์˜ ์กฐ๊ฑด์„ ์ž˜ ์„ค์ •ํ•ด ์ฃผ์–ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค.

import java.util.*;

public class Programmers_169199 {
    static int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // ์ƒํ•˜์ขŒ์šฐ
    static char[][] map; // ๊ฒŒ์ž„ํŒ
    static boolean[][] visited; // ๋ฐฉ๋ฌธ ์—ฌ๋ถ€
    static int[] start = new int[2]; // ์‹œ์ž‘์  ์ขŒํ‘œ ์ •๋ณด

    public static int solution(String[] board) {
        map = new char[board.length][board[0].length()];
        visited = new boolean[board.length][board[0].length()];
        Queue<int[]> queue = new LinkedList<>(); // bfs๋ฅผ ๊ตฌํ˜„ํ•  ํ ์ƒ์„ฑ

        // ๊ฒŒ์ž„ํŒ ์ €์žฅ
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length(); j++) {
                map[i][j] = board[i].charAt(j);

                // ์‹œ์ž‘์  ์ €์žฅ
                if (map[i][j] == 'R') {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }

        queue.offer(start); // ์‹œ์ž‘์  ์ž…๋ ฅ
        visited[start[0]][start[1]] = true; // ์‹œ์ž‘์  ๋ฐฉ๋ฌธ ์—ฌ๋ถ€ ํ‘œ์‹œ

        int count = 0; // ์ด๋™ ํšŸ์ˆ˜

        while(!queue.isEmpty()) {
            count++;
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                // ํ˜„์žฌ ์œ„์น˜
                int[] current = queue.poll(); 
                for (int j = 0; j < 4; j++) {
                    // ํ˜„์žฌ ์ขŒํ‘œ
                    int curX = current[0];
                    int curY = current[1];

                    // ํ•ด๋‹น ๋ฐฉํ–ฅ์œผ๋กœ ์ง„ํ–‰
                    while (curX + direction[j][0] >= 0 && curX + direction[j][0] < board.length &&
                    curY + direction[j][1] >= 0 && curY + direction[j][1] < board[0].length() &&
                    map[curX + direction[j][0]][curY + direction[j][1]] != 'D') {
                        curX = curX + direction[j][0]; // X์ขŒํ‘œ ์ด๋™
                        curY = curY + direction[j][1]; // Y์ขŒํ‘œ ์ด๋™
                    }
                    
                    // ๋ชฉ์ ์ง€์— ๋„์ฐฉํ•œ ๊ฒฝ์šฐ count ๋ฆฌํ„ด
                    if (map[curX][curY] == 'G') {
                        return count;
                    }

                    // ์žฅ์• ๋ฌผ์— ๋ง‰ํžŒ ๊ฒฝ์šฐ
                    if (!visited[curX][curY]) {
                        queue.add(new int[] {curX, curY});
                        visited[curX][curY] = true;
                    }
                }
            } 

        }

        return -1;
    }

}

๐Ÿ‘พ์ฝ”๋“œ ์„ค๋ช…

  1. ๊ฒŒ์ž„ํŒ ์ •๋ณด๋ฅผ 2์ฐจ์› ๋ฐฐ์—ด map์— ์ €์žฅํ•˜๊ณ , ์‹œ์ž‘์  ์ขŒํ‘œ๋ฅผ start๋ฐฐ์—ด์— ์ €์žฅํ•œ๋‹ค.

  2. ์‹œ์ž‘์  ์ขŒํ‘œ๋ฅผ ํ์— ๋„ฃ์–ด์ฃผ๊ณ , ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ์ €์žฅํ•˜๋Š” visited ๋ฐฐ์—ด์— ์‹œ์ž‘์  ์ขŒํ‘œ์˜ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ์ €์žฅํ•ด ์ค€๋‹ค.

  3. ์ด๋™ ํšŸ์ˆ˜๋ฅผ 1์ฆ๊ฐ€ ์‹œํ‚ค๊ณ , ํ˜„์žฌ ์ขŒํ‘œ์—์„œ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ์‚ดํŽด๋ณด์•˜์„ ๋•Œ, ์ด๋™ํ•  ์ขŒํ‘œ๊ฐ€ ๊ฒŒ์ž„ํŒ ๋ฒ”์œ„ ์•ˆ์— ์žˆ๊ณ , ์žฅ์• ๋ฌผ์ด ์žˆ๋Š” ์œ„์น˜๊ฐ€ ์•„๋‹Œ ์กฐ๊ฑด ๋‚ด์—์„œ ํ˜„์žฌ ์ขŒํ‘œ๋ฅผ ์ด๋™์‹œํ‚จ๋‹ค.

  4. ๋ชฉ์ ์ง€์— ๋„์ฐฉํ•œ ๊ฒฝ์šฐ์—๋Š” ๋” ์ด์ƒ ์ง„ํ–‰ํ•  ํ•„์š”๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์— count๋ฅผ ๋ฐ”๋กœ ๋ฆฌํ„ดํ•ด์ค€๋‹ค.

  5. ์žฅ์• ๋ฌผ์— ๋ง‰ํžŒ ๊ฒฝ์šฐ์—๋Š” ํ์— ํ˜„์žฌ ์ขŒํ‘œ๋ฅผ ์ €์žฅํ•˜๊ณ , 3~4๋ฒˆ ๊ณผ์ •์„ ๋‹ค์‹œ ๊ฑฐ์น˜๋ฉฐ ์ด๋™์„ ๊ณ„์† ์ง„ํ–‰ํ•œ๋‹ค.


๐Ÿ”—๋ฌธ์ œ ๋งํฌ
๐Ÿ’ปRepository

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

1๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 8์›” 24์ผ

โ™Ÿ๏ธ์ด๋ ‡๊ฒŒ ๋จธ๋ฆฌ ์•„ํ”ˆ ๋ณด๋“œ๊ฒŒ์ž„์ด๋ผ๋‹ˆ๐Ÿค”

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ