문제 링크

문제 링크

문제 설명

제한 사항 및 입출력 예

입출력 예 설명

풀이

1. bfs로 풀자
2. 일반 bfs지만, 벽또는 장애물(D)를 만나기전까지 이동한다 라는 로직만 구현하면 되는 bfs다.

처음엔 문제 풀이가 부족하다고 생각했지만, 문제를 이해하고보면 문제에서 해줄 설명은 다 해줬다고 생각한다.

문제에 대해 더이상의 설명은 필요가 없다?라는 뜻이다.

나는 이런 알고리즘 문제를 볼때마다 한 고객의 요구사항이라고 생각하려한다.

현업의 고객 요구사항은 RFP를 가지고 직접 인터뷰를 하는 와중에도 적힌 요구사항에 대해 몇번이고 내부적으로 회의하자며 요구사항에 대한 명확한 정의는 추후로 미루기도한다.

RFP = 고객의 요구사항이 담긴 한글파일 나라장터가면 수두룩하게 볼 수 있음

물론 이런 문제풀이에 쓰이는 알고리즘 역량은 현업과 직접적인 연관은 없다 ㅋㅋㅋ 근데 난 이걸 잘하고싶다.

취업준비생때도 난 알고리즘을 정복하고싶었다. 그러나 당시엔 자소서, 포트폴리오, 어학 등과 같이 다른 요소들과의 시간투자에 대한 가성비를 따지다가 진득하게 준비하진 못했다.

지금와서 이런 문제를 푸는것도, 그때 정복하지 못했던 알고리즘에 대해 지금이라도 잘하고싶다고 느꼈기 때문이다 ㅋㅋ

여하튼, 현업의 요구사항에 비하면 이런 알고리즘 문제는 얼마나 세세한 요구사항일까 되새기며 문제를 이해해야겠다.

코드

import java.util.*;
class Pos {
    int x, y;
    int level;
    Pos(int x, int y, int level) {
        this.x = x;
        this.y = y;
        this.level = level;
    }
}
class Solution {
    public char[][] map;
    public boolean[][] visited;
    public int[] dx = {-1, 0, 1, 0};
    public int[] dy = {0, 1, 0, -1};
    public Pos getPos(int index, Pos now) {
        int x = now.x , y = now.y;
        int ix = dx[index];
        int iy = dy[index];
        while(x + ix >= 0 && x + ix < map.length 
              && y + iy >= 0 && y + iy < map[0].length
                && map[x + ix][y + iy] != 'D') 
        {
            x += ix;
            y += iy;
        }

        return new Pos(x, y, now.level + 1);
    }
    public int bfs(Pos start, Pos goal) {
        Queue<Pos> q = new LinkedList<>();
        visited[start.x][start.y] = true;
        q.add(start);
        while(!q.isEmpty()) {
            Pos now = q.poll();
            int x = now.x;
            int y = now.y;
            int level = now.level;
            if(x == goal.x && y == goal.y)
                return level;
            for(int i = 0; i < 4; i++) {
                Pos next = getPos(i, now);            
                if(!visited[next.x][next.y]) {
                    visited[next.x][next.y] = true;
                    q.add(next);
                }
            }
        }
        return -1;
    }
    public int solution(String[] board) {
        int answer = 0;
        map = new char[board.length][board[0].length()];
        visited = new boolean[map.length][map[0].length];
        Pos start = null;
        Pos goal = null;
        for(int i = 0; i < map.length; i++) {
            for(int j = 0; j < map[0].length; j++) {
                map[i][j] = board[i].charAt(j);
                if(map[i][j] == 'R')
                    start = new Pos(i, j, 0);
                if(map[i][j] == 'G')
                    goal = new Pos(i, j, 0);
            }
        }
        answer = bfs(start, goal);
        return answer;
    }
}