글 읽기 - 로직에 문제가 있는걸까요? 도와주세요.ㅠ

quro07 4년 전 0

로직에 문제가 있는걸까요? 도와주세요.ㅠ

어떤 부분이 빠졌는지 모르겠네요...

package alg;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, M, answ = -1;
	public static int[][] map = new int[1001][1001];
	public static int[][][] visited = new int[1001][1001][3];
	public static int[] cy = {-1, 0, 1, 0};
	public static int[] cx = {0, -1, 0, 1};
	public static Queue<Node> q = new LinkedList<Node>();
	
	public static class Node{
		int y, x, cost, isWall;
		public Node(int _y, int _x, int _cost, int _isWall) {
			this.y = _y; this.x = _x;
			this.cost = _cost; this.isWall = _isWall;
		}
	}
	
	private static boolean isWrong(int y, int x) {
		if (y<0 || y>=N || x<0 || x>=M)
			return true;
		return false;
	}
	
	private static void BFS() {
		q.add(new Node(0,0,1,0));
		
		while(!q.isEmpty()) {
			Node node = q.peek(); q.remove();
			
			if(node.y == N-1 && node.x == M-1) {
				answ = node.cost;
				return;
			}
			
			for(int i=0; i<4; i++) {
				int ny = node.y + cy[i];
				int nx = node.x + cx[i];
				int ncost = node.cost + 1;
				int isWall = node.isWall;
				
				if(isWrong(ny, nx))
					continue;
				
				//벽이 없을때
				if(map[ny][nx] == 0) {
					if(visited[ny][nx][0] == 1) 
						continue;
					visited[ny][nx][0] = 1;
					q.add(new Node(ny, nx, ncost, isWall));
				}
				
				//벽이 있을때
				if(map[ny][nx] == 1) {
					if(visited[ny][nx][1] == 1) 
						continue;
					if(isWall == 1) 
						continue;
					visited[ny][nx][1] = 1;
					q.add(new Node(ny, nx, ncost, 1));
				}
				
			}
			
		}
		
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		//input
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<N; i++) {
			String str = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		
		//logic
		BFS();
		
		//output
		System.out.println(answ);
		
	}

}

quro07 4년 전 0

해결했습니다..

멍청하게도..

if(map[ny][nx] == 0) {

if(visited[ny][nx][0] == 1)
continue;

visited[ny][nx][0] = 1;

q.add(new Node(ny, nx, ncost, isWall));

}

이부분에서 현재 상태로 체크를 해야하는데 그렇지 않은게 원인이였네요.

누군가 보신다면 도움되길 바랍니다.

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

문제

문제

출처

ICPC

로직에 문제가 있는걸까요? 도와주세요.ㅠ

quro07 4년 전 0

quro07 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말