글 읽기 - 무엇이 잘못되었을까요ㅠㅠ

zz4471 2년 전 0

방문여부(visit[][])을 boolean이 아닌 int로 해서
벽을 뚫지 않고 온 놈이 이미 있음(visit[][] == 0),
벽을 하나 뚫고 온 놈이 이미 있음(visit[][] == 1),
(두 경우 전부 지나간 경우 visit[][] == 2)
이 두 상태를 체크해서 해결하려고 했는데요

논리나 코드에 틀린점이 있다면 조언 부탁드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class Node {
    int y;
    int x;
    int depth;
    int usedNum;

    Node(int y, int x, int depth, int usedNum) {
        this.y = y;
        this.x = x;
        this.depth = depth;
        this.usedNum = usedNum;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");
        int colN = Integer.parseInt(split[0]);
        int rowM = Integer.parseInt(split[1]);
        int[][] map = new int[colN][rowM];
        int[][] visit = new int[colN][rowM];
        for(int i = 0; i < colN; i++) {
            split = br.readLine().split("");
            for(int j = 0; j < rowM; j++) {
                map[i][j] = Integer.parseInt(split[j]);
                visit[i][j] = Integer.MAX_VALUE;
            }
        }

        Queue<Node> q = new LinkedList<>();
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        q.offer(new Node(0, 0, 1, 0));
        visit[0][0] = 0;

        int answer = -1;
        while(true) {
            if(q.isEmpty()) {
                break;
            }

            Node now = q.poll();
            if(now.y == colN -1 && now.x == rowM -1) {
                answer = now.depth;
                break;
            }
            for(int i = 0; i < 4; i++) {
                int tempY = now.y + dir[i][0];
                int tempX = now.x + dir[i][1];

                if(tempY < 0 || tempY >= colN || tempX < 0 || tempX >= rowM)
                    //범위를 벗어났다
                    continue;
                if(visit[tempY][tempX] == now.usedNum || visit[tempY][tempX] == 2)
                    //먼저온 같은 종류(하나 뚫고온 놈, 한 번도 안뚫고 온 놈)가 있다
                    //두 종류 모두 이미 지나갔다 
                    continue;
                if(map[tempY][tempX] == 1) {
                    if(now.usedNum == 1)
                        //벽인데 더 이상 뚫을 수 없다
                        continue;
                    else {
                        now.usedNum = 1;
                    }
                }

                q.offer(new Node(tempY, tempX, now.depth +1, now.usedNum));
                if(visit[tempY][tempX] == Integer.MAX_VALUE)
                    //한 종류의 놈만 지나간 경우
                    visit[tempY][tempX] = now.usedNum;
                else
                    //두 종류의 놈 전부 지나간 경우
                    visit[tempY][tempX] = 2;
            }
        }

        System.out.println(answer);
    }
}

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

문제

문제

출처

ICPC

무엇이 잘못되었을까요ㅠㅠ

zz4471 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말