물놀이를 가자 SWEA#10966

D4

문제 이해

• N x M의 그리드가 주어진다
  • 1 <= N, M <= 1000
• 셀은 'W' 물 또는 'L'이다
• 각 땅 셀에서 물 셀로의 최소 거리를 구하여라

해결방안 고안

모든 물 셀에서부터 땅 셀까지의 거리를 구하면 각 땅 셀에서 물 셀까지의 거리를 구한 것과 마찬가지죠.

각 땅 셀에서부터 물 셀까지의 거리를 계산하면 모든 땅 셀에 대해 모두 BFS를 처리해줘야하는 반면에, 모든 물셀에서부터의 땅 셀의 거리를 계산하면 물 셀들 개수만큼만 BFS를 하고, 이미 방문된 땅 셀은 가지치기 될 수 있어서 더 효율적이죠.

풀이 코드

SWEA 물놀이를 가자

---

치즈 백준#2636

문제 이해

• N x M 그리드에 1 (치즈)와 0 (빈칸)이 주어진다
• 1시간마다 가장자리의 치즈만 녹는다
• 모든 치즈가 녹는데 걸리는 시간을 구하라
• 모든 치즈가 녹기 전 남아있던 치즈 셀의 개수를 구하라

해결방안 고안

무조건 빈 셀인 (0, 0)부터 매시간 BFS를 하면 가장자리인 치즈를 찾을 수 있다.

치즈를 만나면 탐색을 멈추고, 빈 칸을 만나면 탐색을 계속해서 빈셀과 인접해 있는 (즉 가장자리인) 치즈를 녹일 수 있다.

static int bfs() {
	ArrayDeque<int[]> queue = new ArrayDeque<>();
	queue.add(new int[]{0, 0});
	int[][] visited = new int[N][M];
	visited[0][0] = 1;
	int melted = 0;
	while (!queue.isEmpty()) {
		int[] node = queue.pollFirst();
		int y =node[0];
		int x = node[1];
		for (int d = 0; d < 4; d++) {
			int ny = y + DY[d];
			int nx = x + DX[d];
			if (isValidCoordinate(ny, nx) && visited[ny][nx] == 0) {
				visited[ny][nx] =1;
				if (grid[ny][nx] == 1) {
					grid[ny][nx] =0;
					melted ++;
				} else {
					queue.add(new int[]{ny, nx});
				}
			}
		}
	}
	cheeseCount -= melted;
	return melted;
}

매번 BFS를 하기 전에 남아있는 치즈의 수를 변수에 저장해 마지막에 출력한다.

int time = 0;
while (cheeseCount > 0) {
	lastCheeseCount = cheeseCount;
	bfs();
	time++;
}     

삽질

구멍의 조건을 충족시키는 셀의 특징을 고민하다가 시간을 허비했다.

---

친구비 백준#16562

문제 이해

• 학생 N명 전원과 친구가 되고 싶다
  • 1 <= N <= 10000
  • 친구 관계 수 M (0 <= M <= 10000)
• 친구 비용은 최소화하고 싶다
• 친구의 친구는 친구다 (비용은 한 번만 든다)

해결 방안 고안

학생 중 친구 관계를 맺을 수 있으면 모두 맺은 다음, 친구 무리 별로 가장 친구비가 저렴한 것을 비용에 포함시킨다.

Kruskal 알고리즘을 사용했다.

makeSet();

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int f1 = Integer.parseInt(st.nextToken());
    int f2 = Integer.parseInt(st.nextToken());
    union(f1, f2);
}

친구 무리를 생성하고 나서 루트 대표자를 갖고 있도록 모두 업데이트시켜준다.

long minCost = 0;
Map<Integer, Long> componentMinCost = new HashMap<>();

for (int i = 1; i <= N; i++) {
	int root = findSet(i);
    componentMinCost.put(root, Math.min(componentMinCost.getOrDefault(root, Long.MAX_VALUE), friendFees[i]));
}

for (long cost : componentMinCost.values()) {
	minCost += cost;
}

친구 무리 별로 가장 가격이 낮은 친구비를 포함시킨다.

풀이코드

친구비 풀이코드

---

녹색 옷 입은 애가 젤다지? 백준#4485

문제 이해

젤다의 전설

젤다

링크

솔직히 젤다의 전설 플레이 처음하는 사람은 링크가 젤다인줄 알 수 있을 것 같음

하여튼 속상한 링크는 그리드 동굴 입장~

• 그리드 N x N의 (0, 0)에서 (N-1, N-1)로 이동하는 최소 비용
  • 2 <= N <= 125
• 한 번에 상하좌우 인접한 곳으로 1칸씩 이동 가능
• 각 셀의 비용은 셀의 값이다
  • 0 이상 9 이하

해결방안

그래프 상에서 노드 간 이 문제의 경우, (0,0)부터 (N-1, N-1)까지 탐색 비용을 최소화하는 알고리즘은 다음과 같다

1. 다익스트라: 한 노드에서 다른 모든 노드까지의 최단 경로 구하기 (음수 가중치 불가)
2. 플로이드 워셜: 한 노드에서 다른 모든 노드까지의 최단 경로 구하기 (음수 사이클 불가, 음수 가중치 가능)
3. 벨만 포드: 모든 노드에서 모든 노드까지의 최단 경로 구하기 (음수 사이클 불가, 음수 가중치 가능)

다익스트라 선택 이유

• 이동 비용이 0이상 9 이하로 제한되어 있음

다익스트라 코드

1. 필요한 자료구조를 모두 초기화한다

boolean[][] visited = new boolean[N][N];
int[][] minCost = new int[N][N];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));

int[][] visited

탐색한 좌표인지 방문 여부를 담을 2D 배열 visited를 초기화한다

int[][] minCost

(y, x) 좌표까지의 최소 비용을 담을 2D 배열 minCost를 초기화한다.

minCost는 여느 최솟값 구하기 문제 풀이와 같이 모든 셀 값을 Integer.MAX_VALUE로 초기화해야 한다

for (int i = 0; i < N; i++) {
    Arrays.fill(minCost[i], INF);
}

시작점 또한 비용이 든다.

minCost[startY][startX] = grid[startY][startX];

PriorityQueue<int[]> pq

매번 최소비용부터 꺼내서 탐색하고 싶기 때문에 최소비용 작은 순으로 정렬할 PriorityQueue를 초기화한다.

int[] a = {y좌표, x좌표, 비용}

시작점을 우선순위큐에 추가한 다음 탐색을 시작한다.

pq.offer(new int[] {startY, startX, minCost[startY][startX]});

2. 다익스트라 알고리즘의 구현

while (!pq.isEmpty()) {
	int[] node = pq.poll(); // 우선순위큐에서 가장 비용이 작은 노드부터 꺼낸다
    int y = node[0];
    int x = node[1];
    int cost = node[2];
    
    if (visited[y][x]) continue; // 이미 방문한 노드면 통과한다
    visited[y][x] = true; // 방문하지 않은 노드면 방문처리부터 한다
    
    if (y == endY && x == endX) return cost; // 목적지에 도착했으면 리턴한다
    
    for (int d = 0; d < 4; d++) {
    	int ny = y + DY[d];
        int nx = x + DX[d];
        
        // 유효한, 아직 방문하지 않은 좌표 && 최소 비용이 현재 비용보다 크면
        if (isValidCoordinate(ny, nx) && !visited[ny][nx] && minCost[ny][nx] > cost + grid[ny][nx]) {
        	// 최소 비용을 업데이트하고, 
            minCost[ny][nx] = cost + grid[ny][nx];
            
            // 큐에 추가해서 추후 방문한다
            pq.offer(new int[] {ny, nx, minCost[ny][nx]});
        }
    }
    return -1;
}

풀이 코드

백준 #4485 풀이 코드

---

말이 되고픈 원숭이 백준#1600

골드3

문제 이해

• H x W 그리드에서 (0,0)부터 (H-1, W-1)으로 이동한다
  • 1 <= W, H <= 200
• 이동 방식은 2가지다
  • 말 이동
    • int[][] HDY = {-1, -2, -2, -1, 1, 2, 2, 1}
    • int[][] HDX = {-2, -1, 1, 2, -2, -1, 1, 2}
    • 최대 K번만 가능 (0 <= K <= 30)
  • 일반 사방 탐색 이동
    • 제한 없음
• 그리드의 셀 값이 1이면 이동 불가

해결방안

이동 방식이 다양하지만 결국 이동의 비용, 즉 가중치는 일정하기 때문에 BFS의 변형이라고 판단한다

BFS 내에서 사방 탐색과 말 탐색 모두를 구현하면 된다.

말 탐색

말 이동은 총 K번만 허용 되기 때문에 현재 노드가 말 이동을 K번 거쳤다면 말 탐색을 수행하지 않는다.

위 조건을 통과했다면 말 이동 (팔방탐색)을 수행한다. visited 배열을 관리하는 것이 관건인데, 이미 방문한 좌표더라도 말 이동을 몇번 했는지에 따라서 거리를 다시 계산할 필요가 있다.

즉, 말 이동 없이 현 좌표에 도착한 경우와 말 이동 1번으로 도착한 경우와, 말 이동 2번으로 도착 한 경우 모두 최단거리가 상이할 수 있기 때문에 말 이동 횟수에 따라서 방문 여부와 이동 거리를 저장해야 한다.

int visited[][][] = new int[H][W][K+1];

방문 배열을 3차 정수 배열로 관리해서 visited[y][x][i] 말 이동 i번으로 도착한 이동거리를 저장한다.

BFS 구현

static int bfs(int startY, int startX, int endY, int endX) {
	ArrayDeque<int[]> queue = new ArrayDeque<>();
    int[][][] visited = new int[H][W][K+1];
    queue.add(new int[]{startY, startX, 0});
    visited[startY][startX][0] = 1;

    while (!queue.isEmpty()) {
        int[] node = queue.pollFirst();
        int y = node[0];         
        int x = node[1];
        int horse = node[2];

        if (y == endY && x == endX) return visited[y][x][horse] -1;

        for (int d = 0; d < 4; d++) {
            int ny = y + DY[d];
            int nx = x + DX[d];
            if (isVisitable(ny, nx) && visited[ny][nx][horse] == 0) {
                visited[ny][nx][horse] = visited[y][x][horse] + 1;
                queue.add(new int[]{ny, nx, horse});
            }
        }

        if (horse < K) {
            for (int d = 0; d < 8; d++) {
                int ny = y + HDY[d];
                int nx = x + HDX[d];
                if (isVisitable(ny, nx) && visited[ny][nx][horse+1] == 0) {
                    visited[ny][nx][horse + 1] = visited[y][x][horse] + 1;
                    queue.add(new int[] {ny, nx, horse + 1});
                }
            }
        }
    }
    return -1;
}

풀이 코드

말이 되고픈 원숭이 풀이 코드

BFS 변형 문제의 이해

BFS 문제를 풀다보면 벽을 1번 부술 수 있는데 최단거리, 말 이동 K번 할 수 있는데 최단거리 등, 조건이 들어가는 최단거리 변형 문제들이 있다.

이럴 때, 조건의 횟수 제한 K에 대하여 visited[H][W][K+1]로 방문 배열을 관리하는 것을 습관화하자.