문제 링크

문제 링크

문제 설명

제한 사항

입출력 예

입출력 예 설명은... 링크타고들어가자

풀이

1. 어떤 맵이 있고, 최단거리를 찾는거면 무조건 BFS를 떠올려보자
2. bfs(시작점 -> 레버) + bfs(레버 -> 도착점)인 BFS 기본문제다!

문제 설명중,

"따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다"

까지 읽었을 때 바로 2번식이 떠오르긴했는데, 바로 다음 문장을 보고

이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다.

"엥? 뭐야 그럼 레버를 굳이 안지나가도 되나..?"라고 생각해서 그냥 시작점에서 끝점 BFS 한번 딱 돌렸다가 시뻘건 결과창을 보았다. ㅋㅋㅋ

예제랍시고 준것도 참 얍삽하게 어차피 레버를 지나는 케이스랑, 레버를 지날 필요가 없는 케이스 두가지를 줬다 ㅡㅡ

시뻘건 결과창을 본 후, 살짝 나의 역심리에 낚였다는 생각이 들었고 만들어놓은 bfs메소드를 두번 호출해서 통과하였다!

코드

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 {
    static char[][] map;
    static boolean[][] visited;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    public int bfs(int startX, int startY, int H, int W, int EndX, int EndY) {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(startX, startY, 0));
        visited[startX][startY] = true;
        while(!q.isEmpty()) {
            Pos now = q.poll();
            int x = now.x;
            int y = now.y;
            int level = now.level;
            if(x == EndX && y == EndY)
            {
                return level;
            }
            
            for(int i = 0; i < 4; i++) {
                int nowX = x + dx[i];
                int nowY = y + dy[i];
                if(nowX < 0 || nowX >= H || nowY < 0 || nowY >= W)
                    continue;
                if(!visited[nowX][nowY] && map[nowX][nowY] != 'X') 
                {
                    q.add(new Pos(nowX, nowY, level + 1));
                    visited[nowX][nowY] = true;
                }
            }
        }
        return -1;
    }
    public int solution(String[] maps) {
        int answer = 0;
        map = new char[maps.length][maps[0].length()];
        visited = new boolean[map.length][map[0].length];
        Pos startPos = null;
        Pos leverPos = null;
        Pos endPos = null;
        for(int i = 0; i < maps.length; i++) {            
            for(int j = 0; j < maps[i].length(); j++) {
                if(maps[i].charAt(j) == 'S')
                    startPos = new Pos(i, j, 0);
                if(maps[i].charAt(j) == 'L')
                    leverPos = new Pos(i, j, 0);
                if(maps[i].charAt(j) == 'E')
                    endPos = new Pos(i, j, 0);
                map[i][j] = maps[i].charAt(j);
            }
        }
        answer = bfs(startPos.x, startPos.y, maps.length, maps[0].length(), leverPos.x, leverPos.y);
        if(answer > -1)
        {
            visited = new boolean[map.length][map[0].length];
            
            int temp = bfs(leverPos.x, leverPos.y, maps.length, maps[0].length(), endPos.x, endPos.y);
            if(temp == -1)
                answer = -1;
            else
                answer += temp;
        }
        return answer;
    }
}

오랜만에 글을 쓰넹 ㅎㅎ (잡담)

회사 일이 너무 바빠서 글을 좀 오랜만에 쓴다

나는 요즘 고객 인터뷰를 주구장창 하고있는데, 고객도 미처 생각하지 못한 부분을 어떻게든 도출해서 더 좋은 결과물을 만드려는 옆의 부장님을 보고, 일적인 부분 외에도 배우는게 많은 나날을 보내고 있다.

참 그리고 ownus 백엔드 구현은 거의 끝났는뎈ㅋㅋㅋ 포스팅을 하려니.. 어떻게 잘라서 포스팅을 해야할지 조금 막막하긴하다.. ㅜㅜ 업로드.. 해야지해야지