• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[백준] 2178번 : 미로 탐색 with python3, java

17 Oct 2018

Reading time ~1 minute

문제: https://www.acmicpc.net/problem/2178

import sys
read = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(100000)

w, h = map(int, read().split())

matrix = [[int(i) for i in read()] for _ in range(w)]
group = [[0]*h for _ in range(w)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

q = [[0,0]]
group[0][0] = 1

while q:
    x, y = q.pop(0)
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx and nx < w and 0 <= ny and ny < h :
            if matrix[nx][ny] == 1 and group[nx][ny] == 0:
                q.append([nx, ny])
                group[nx][ny] = group[x][y] + 1

print(group[w-1][h-1])

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
//

class Pair{
    int x;
    int y;
    Pair(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main {
    public static Scanner sc = new Scanner(System.in);
    public static int[] dx = {0,1,0,-1};
    public static int[] dy = {1,0,-1,0};
    public static void main(String args[]){
        int x = sc.nextInt();
        int y = sc.nextInt();

        int[][] table = new int [x][y];
        sc.nextLine();

        for(int i = 0;i<x;i++){
            String s = sc.nextLine(); //라인으로 받았으니 String으로 하는구나
            for(int j=0;j<y;j++){
                table[i][j] = s.charAt(j) - '0';
            }
        }

        int[][] distance = new int[x][y];
        boolean[][] check = new boolean[x][y];
        Queue<Pair> q = new LinkedList<Pair>();

        distance[0][0] = 1;
        check[0][0] = true;
        q.add(new Pair(0,0));

        while(!q.isEmpty()){
            Pair p = q.remove();
            int beforeX = p.x; //x좌표
            int beforeY = p.y; //y 좌표

            for(int k = 0;k<4;k++){

                int afterX = beforeX+dx[k];
                int afterY = beforeY+dy[k];
                if( (afterX >=0)&&(afterY>=0)&&(afterX<x)&&(afterY<y)){
                    if((check[afterX][afterY] == false) && (table[afterX][afterY]==1)){
                        distance[afterX][afterY] = distance[beforeX][beforeY]+1;
                        q.add(new Pair(afterX,afterY));
//                        다음 노드를 for문으로 충분히 넣는다!
                        check[afterX][afterY] = true;

                    }
                }
            }

        }

        System.out.println(distance[x-1][y-1]);


    }
}


algorithm백준pythonjava Share Tweet +1