[Java, Python] SWEA 1226번 미로1

문제

아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.

가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.

주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.

아래의 예시에서는 도달 가능하다.

 

 

아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다.

[입력]

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).

 

파이썬 풀이

# 사방탐색을 하기 위한 방향리스트
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(start):
    q = [start]		# 시작점을 큐에 저장
    while q:		# 큐에 값이 들어있는한 아래 과정을 반복한다.
        x, y = q.pop(0)			# 큐에 저장되어있는 좌표를 뽑아온다.
        for i in range(4):		# 현재 좌표를 기준으로 사방탐색을 실시
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 16 and 0 <= ny < 16:		# 탐색한 좌표가 미로를 벗어나는지 체크
                if maze[nx][ny] == 3:				# 탐색한 좌표의 값이 3인경우 출발점에 도달했기 때문에 
                    return 1						# 1을 리턴한다.

                if maze[nx][ny] == 0:		# 탐색한 좌표가 아직 방문하지 않은 경우
                    maze[nx][ny] = 1		# 해당 노드를 방문하고 값을 1로 수정, 다시 방문하지 않기 위해
                    q.append([nx, ny])		# 해당 좌표를 다시 큐에 저장한다.
    return 0		# while 문이 끝나는 경우 도착점에 방문하지 못했기 때문에 0을 리턴한다.

for _ in range(10):
    tc = int(input())
    maze = list(list(map(int, input().strip())) for _ in range(16))

    start = [0, 0]		# 시작위치

	# 시작위치를 찾기 위한 이중 for문, 값이 2인 경우 행과 열의 인덱스 값을 start 변수에 저장했다.
    for i in range(16):
        for j in range(16):
            if maze[i][j] == 2:
                start = [i, j]

    print(f"#{tc} {bfs(start)}")

 

자바 풀이

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

// 좌표 정보를 담고 있는 포인트 class
class Point {
    int x, y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    // 사방 탐색을 하기 위한 방향 리스트 sol 메소드에서 바로 사용하기 위해 static으로 선언
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    
    public int sol (int x, int y, int[][] maze) {
        Queue<Point> q = new LinkedList<>();		// bfs를 구현하기 위한 큐 생성
        q.offer(new Point(x, y));					// 큐에 시작 노드 저장
        maze[x][y] = 1;								// 방문 표시로 해당 좌표 값을 1로 수정
        while (!q.isEmpty()) {					// 큐에 값이 있는한 아래 과정 반복
            Point cur = q.poll();				// 현재 좌표값을 뽑아온다.
            for (int i = 0; i < 4; i++) {		// 사방탐색 실시
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                // 미로의 크기를 벗어나지 않으면서 방문하지 않은 경우 체크
                // 값이 3인 경우도 탐색을 해야하기 때문에 maze[nx][ny] == 0이 아닌 maze[nx][ny] != 1로 체크
                if (nx >= 0 && nx < 16 && ny >= 0 && ny < 16 && maze[nx][ny] != 1) {
                    if (maze[nx][ny] == 3) {		// 현재 노드의 값이 3인경우 1 리턴
                        return 1;
                    }
                    q.offer(new Point(nx, ny));		// 다시 현재 노드의 좌표를 큐에 저장
                    maze[nx][ny] = 1;				// 방문 표시
                }
            }
        }
        return 0;		// 여기까지 왔으면 도착점에 도달하지 못했다는 의미이기 때문에 0을 리턴한다.
    }
 
    public static void main(String[] args) {
        Solution m = new Solution();			// Solution 객체 생성
        Scanner sc = new Scanner(System.in);	// 입력값을 받기 위한 작업
        for (int t = 1; t <= 10; t++) {
            int tc = sc.nextInt();
            int[][] maze = new int[16][16];		// 미로 생성
            for (int i = 0; i < 16; i++) {
                String row = sc.next();			// 미로 정보를 한줄로 받고
                for (int j = 0; j < 16; j++) {
                    maze[i][j] = row.charAt(j) - '0';		// 미리 생성한 maze 2차원 배열에 저장
                }
            }
 
 			// 시작점을 찾는 과정
            int si = 0, sj = 0;
            for (int i = 0; i < 16; i++) {
                for (int j = 0; j < 16; j++) {
                    if (maze[i][j] == 2) {
                        si = i;
                        sj = j;
                    }
                }
            }
            System.out.println("#" + tc + " " + m.sol(si, sj, maze));
        }
    }
}