글 읽기 - 벽 부수고 이동하기 중 벽 부수기 질문

qotnals1320 4년 전 0

미로찾기랑 거의 유사한 문제인데 어떻게 풀어야 할지를 몰라서 답을 보던 중에 int 배열visit을 선언해서 벽을 부수는 것을 최단 경로로 가져가기 위해서 갱신해나간다고 하였는데 이 말이 무슨 말인지 잘 이해가 가질 않습니다. 혹시 벽 부수는 과정을 이해시켜 주실분 계신가요..

코드 출처는 https://kim6394.tistory.com/201 여기입니다.

public static void bfs(int y, int x) {
        
        Queue<Place> q = new LinkedList<>();
        
        q.add(new Place(y, x, 1, 0)); // y좌표, x좌표, 이동거리, 공사횟수
        visit[y][x] = 0; // 처음 공사횟수
        
        while(!q.isEmpty()) {
            
            Place p = q.poll();
            
            // 도착지점 만나면 종료
            if(p.y == N-1 && p.x == M-1){
                ans = p.dis;
                break;
            }
            
            for (int i = 0; i < 4; i++) {
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];
                
                if(ny<0 || nx<0 || ny>=N || nx>=M) continue;
                
                if(visit[ny][nx] <= p.drill) continue;
                
                if(map[ny][nx] == 0) { // 벽이 아닐 때
                    visit[ny][nx] = p.drill;
                    q.add(new Place(ny, nx, p.dis+1, p.drill));
                }
                else { // 벽일 때
                    if(p.drill == 0){
                        visit[ny][nx] = p.drill + 1;
                        q.add(new Place(ny, nx, p.dis+1, p.drill+1));
                    }
                }
            }
            
        }
        
    }

wjddydgns99 4년 전 1

벽을 부서서(문제조건 : 1개까지) 최단거리일 수 있고 안부신 것이 최단거리일 수 있잖아요?

벽을 2개이상 부셔야만 한다면 -1출력하시면 되고요.

미로찾기보다는 알고스팟 문제를 풀어보고 이 문제를 풀어보면 도움 될거에요.

wjddydgns99 4년 전 1

https://www.acmicpc.net/problem/1261

wjddydgns99 4년 전 1

예시 하나 생각해봤는데요.

5 5

01100

01000

01110

01000

00010

출력 : 9

출력 값은 벽을 1개 깬 것이잖아요?

{가로 x, 세로 y (x,y)이면}

벽을 깨지 않는다면 (0,0) -> (0,4) --> (2,4) --> (2,3) --> (4,3) --> (4,4) 로 이동할 것인데 벽을 1개 깨서 최소거리는 9가 출력돼요.

qotnals1320 4년 전 0

알려주셔서 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

벽 부수고 이동하기 중 벽 부수기 질문

qotnals1320 4년 전 0

wjddydgns99 4년 전 1

wjddydgns99 4년 전 1

wjddydgns99 4년 전 1

qotnals1320 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말