글 읽기 - 제가 문제가 이해가 안가서 그러는데요 ㅜㅜ

gmldud9605 2년 전 0

bfs로 s부터 k까지 거리 더해주는식으로 짯는데 왜 mst를 써야 하는지 모르겠어요 반례나 문제좀 이해시켜 주시면 감사하겠습니다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 복제 로봇
public class BakJoon1944 {
    static int N, M;
    static char[][] area;
    static int[][] visit;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static Queue<Point> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        area = new char[N][N];
        visit = new int[N][N];
        for (int h = 0; h < N; h++) {
            String input = br.readLine();
            for (int w = 0; w < N; w++) {
                area[w][h] = input.charAt(w);
                if (area[w][h] == 'S') {
                    queue.add(new Point(w, h));
                    visit[w][h] = 0;
                }
            }
        }

        bfs();

        int keyFindCount =0;
        int dist = 0;
        for(int h=0;h<N;h++){
            for(int w=0;w<N;w++){
                if (area[w][h] == 'K' && visit[w][h] != 0){
                    keyFindCount++;
                    dist += visit[w][h];
                }
            }
        }
        if (keyFindCount == M) System.out.println(dist);
        else System.out.println(-1);
    }

    static void bfs() {
        while (!queue.isEmpty()) {
            Point check = queue.poll();
            //System.out.println(check.x + " " + check.y);

            for (int i = 0; i < 4; i++) {
                int nx = check.x + dx[i];
                int ny = check.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (area[nx][ny] == '1') continue;
                if (visit[nx][ny] != 0) continue;
                queue.add(new Point(nx, ny));
                visit[nx][ny] = visit[check.x][check.y] + 1;
            }
        }
    }
}

star2user 2년 전 0

5 3

11111

1S1K1

10001

1K1K1

11111

8출력

6 4
111111
1000K1
10S0K1
1000K1
10K001
111111

6출력

님이 짠 방식은 K1 바로 옆에 K2가있을때 K1도달후 K2를 바로 가는게아니고 K1도달후 다시 S에서시작하여 K2 도달하는 방식아닌가요

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

문제

문제

출처

ICPC

제가 문제가 이해가 안가서 그러는데요 ㅜㅜ

gmldud9605 2년 전 0

star2user 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말