FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

python-for-coding-test/5/11.java at master · ndb796/python-for-coding-test · GitHub

79 lines (65 loc) · 2.22 KB

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

import java.util.*;

class Node {

private int x;

private int y;

public Node(int x, int y) {

this.x = x;

this.y = y;

}

public int getX() {

return this.x;

}

public int getY() {

return this.y;

}

}

public class Main {

public static int n, m;

public static int[][] graph = new int[201][201];

// 이동할 네 가지 방향 정의 (상, 하, 좌, 우)

public static int dx[] = {-1, 1, 0, 0};

public static int dy[] = {0, 0, -1, 1};

public static int bfs(int x, int y) {

// 큐(Queue) 구현을 위해 queue 라이브러리 사용

Queue<Node> q = new LinkedList<>();

q.offer(new Node(x, y));

// 큐가 빌 때까지 반복하기

while(!q.isEmpty()) {

Node node = q.poll();

x = node.getX();

y = node.getY();

// 현재 위치에서 4가지 방향으로의 위치 확인

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

int nx = x + dx[i];

int ny = y + dy[i];

// 미로 찾기 공간을 벗어난 경우 무시

if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

// 벽인 경우 무시

if (graph[nx][ny] == 0) continue;

// 해당 노드를 처음 방문하는 경우에만 최단 거리 기록

if (graph[nx][ny] == 1) {

graph[nx][ny] = graph[x][y] + 1;

q.offer(new Node(nx, ny));

}

}

}

// 가장 오른쪽 아래까지의 최단 거리 반환

return graph[n - 1][m - 1];

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

// N, M을 공백을 기준으로 구분하여 입력 받기

n = sc.nextInt();

m = sc.nextInt();

sc.nextLine(); // 버퍼 지우기

// 2차원 리스트의 맵 정보 입력 받기

for (int i = 0; i < n; i++) {

String str = sc.nextLine();

for (int j = 0; j < m; j++) {

graph[i][j] = str.charAt(j) - '0';

}

}

// BFS를 수행한 결과 출력

System.out.println(bfs(0, 0));

}

}

Back | FazBrowse Home | New Git URL