투로드
Coder ToLoad
투로드
전체 방문자
오늘
어제

블로그 메뉴

  • 홈
  • 알고리즘
  • CS
  • GITHUB
  • 태그
  • 분류 전체보기 (69)
    • Toy Project (0)
      • EternalSNS (0)
    • Algorithm (46)
      • BaekJoon (38)
      • Programmers (7)
      • Code Tree (1)
    • Computer Science (13)
      • JAVA (7)
      • DataBase (4)
    • Backend (7)
      • Spring (2)
      • JPA (2)
      • Django (3)
    • Mobile (2)
      • Android (2)
    • Unity (1)

인기 글

최근 글

hELLO · Designed By 정상우.
투로드

Coder ToLoad

Algorithm/BaekJoon

[JAVA] 백준 1261 : 알고스팟

2021. 4. 2. 18:07
문제
 

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미

www.acmicpc.net

 

해결 방법

다익스트라 알고리즘을 사용해서 풀어야 합니다.

다익스트라 알고리즘은 A에서 B로 가는 것의 최단 거리를 구할 때 주로 사용합니다.

이 문제에서는 시작 지점과 끝 지점이 지정되어있고, 구해야 하는 벽을 부순 횟수가 

음수로 존재하지 않기 때문에 사용이 가능합니다.

 

코드는 다익스트라 알고리즘을 그대로 구현한 것이라 따로 설명하진 않겠습니다.

 

아래 링크의 분이 잘 설명해두셔서 참조 남깁니다.

 

[알고리즘/자바] 다익스트라 알고리즘 (Dijkstra Algorithm)

이름만 들어도 어려울 것만 같은 다익스트라... 컴퓨터 과학자 에츠허르 데이크스트라 이름을 따서 만들었다고 한다. (나도 내 이름을 딴 알고리즘 만들고 싶다...ㅎㅎ) 어쨌든 어렵다고 생각했

gaybee.tistory.com

 

코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {
	static int dist[][];
	static int array[][];
	static int N, M;
	static int result = 0;
	
	static int dx[] = {0, 0, 1, -1};
	static int dy[] = {-1, 1, 0, 0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		array = new int[N][M];
		for (int i = 0; i < N; i++) {
			String a = br.readLine();
			for (int j = 0; j < M; j++) {
				array[i][j] = a.charAt(j) - '0';
				// char형을 int로 변환할 때 위와 같이 사용
			}
		}
		
		dist = new int[N][M];
		for (int i = 0; i < N; i++) {
			Arrays.fill(dist[i],Integer.MAX_VALUE);
			// dist 배열을 모두 최댓값으로 지정
		}
		
		
		dijkstra();
		
		System.out.println(result);
	
	}
	
	static void dijkstra() {
		PriorityQueue<Node> q = new PriorityQueue<>();
		q.offer(new Node(0, 0, 0));
		dist[0][0] = 0;
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			if (node.x == N - 1 && node.y == M - 1) {
				result = node.broken;
                // 가장 먼저 목적지에 도착한 값이 최솟값이기 때문에
                // 바로 return 해주면 됩니다
				return;
			}
			
			for (int i = 0; i < 4; i++) {
				int newX = node.x + dx[i];
				int newY = node.y + dy[i];
				
				if (newX >= 0 && newX < N && newY >=0 && newY < M) {
					// 1인 벽을 지나갈 때 부숴야하는 횟수가 1 증가하기에 아래와 같이 조건 설정 가능
					if (dist[newX][newY] > dist[node.x][node.y] + array[newX][newY]) {
						dist[newX][newY] = dist[node.x][node.y] + array[newX][newY];
						
						q.offer(new Node(newX, newY, dist[newX][newY]));
					}
				}
			}
		}
		
	}
}

class Node implements Comparable<Node> {
	int x;
	int y;
	int broken;
	
	Node (int x, int y, int broken) {
		this.x = x;
		this.y = y;
		this.broken = broken;
	}

	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return broken - o.broken;
	}
}

'Algorithm > BaekJoon' 카테고리의 다른 글

[JAVA] 백준 11779 : 최소비용 구하기 2  (0) 2021.04.05
[JAVA] 백준 4485 : 녹색 옷 입은 애가 젤다지?  (0) 2021.04.02
[JAVA] 백준 2933 : 미네랄, 18500 : 미네랄2  (0) 2021.03.29
[JAVA] 백준 2776 : 암기왕  (0) 2021.03.25
[JAVA] 백준 1620 : 나는야 포켓몬 마스터 이다솜  (0) 2021.03.24
    'Algorithm/BaekJoon' 카테고리의 다른 글
    • [JAVA] 백준 11779 : 최소비용 구하기 2
    • [JAVA] 백준 4485 : 녹색 옷 입은 애가 젤다지?
    • [JAVA] 백준 2933 : 미네랄, 18500 : 미네랄2
    • [JAVA] 백준 2776 : 암기왕
    투로드
    투로드
    훌륭한 프로그래머가 되어가는 과정을 담아보는 중입니다.

    티스토리툴바