백준 17144번 - 미세먼지 안녕! (Go)

https://www.acmicpc.net/problem/17144

분석

이 문제는 미세먼지가 확산되고, 공기청정기가 바람을 일으켜 청소하는 과정을 시뮬레이션 하는 문제입니다.

 

알고리즘 과정을 생각해보면

1. 미세먼지 확산 (spread 함수) 은 모든 칸이 동시에 확산되므로, 원본 배열을 수정하는 것 보단 새로운 배열을 만들어 원본 배열에 반영합니다.
2. 청소 (clean 함수) 는 바람이 불어오는 역순으로 탐색해야 합니다.
3. 최종 결과를 합산합니다.

시간 복잡도는 모든 칸을 순회하고, t 만큼 반복하므로 O(t * r * c) 입니다.

6 <= r, c <= 50 이고, 1 <= t <= 1000 이므로 50 * 50 * 1000 = 2,500,000 번 이므로 시간 제한 1초 보다 여유롭습니다.

 

공간 복잡도는 2차원 배열 2개를 사용하므로 O(r * c) 입니다.

풀이 코드

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	r, c, t int
	grid [][]int
	robot []int
	dr = []int{0, 0, 1, -1}
	dc = []int{1, -1, 0, 0}
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	fmt.Fscan(in, &r, &c, &t)
	grid = make([][]int, r)

	for i := 0; i < r; i++ {
		grid[i] = make([]int, c)

		for j := 0; j < c; j++ {
			fmt.Fscan(in, &grid[i][j])

			if grid[i][j] == -1 {
				robot = append(robot, i)
			}
		}
	}

	for i := 0; i < t; i++ {
		spread()
		clean()
	}

	res := 0
	for i := 0; i < r; i++ {
		for j := 0; j < c; j++ {
			if grid[i][j] > 0 {
				res += grid[i][j]
			}
		}
	}

	fmt.Fprintln(out, res)
}

func spread() {
	temp := make([][]int, r)

	for i := range temp {
		temp[i] = make([]int, c)
	}

	for i := 0; i < r; i++ {
		for j := 0; j < c; j++ {
			if grid[i][j] > 0 {
				dust := grid[i][j] / 5

				cnt := 0
				for d := 0; d < 4; d++ {
					nr, nc := i + dr[d], j + dc[d]

					if nr >= 0 && nr < r && nc >= 0 && nc < c && grid[nr][nc] != -1 {
						temp[nr][nc] += dust
						cnt++
					}
				}

				grid[i][j] -= dust * cnt
			}
		}
	}

	for i := 0; i < r; i++ {
		for j := 0; j < c; j++ {
			grid[i][j] += temp[i][j]
		}
	}
}

func clean() {
	up := robot[0]

	for i := up - 1; i > 0; i-- {
		grid[i][0] = grid[i - 1][0]
	}

	for i := 0; i < c - 1; i++ {
		grid[0][i] = grid[0][i + 1]
	}

	for i := 0; i < up; i++ {
		grid[i][c - 1] = grid[i + 1][c - 1]
	}

	for i := c - 1; i > 1; i-- {
		grid[up][i] = grid[up][i - 1]
	} 

	grid[up][1] = 0

	down := robot[1]

	for i := down + 1; i < r - 1; i++ {
		grid[i][0] = grid[i + 1][0]
	}

	for i := 0; i < c - 1; i++ {
		grid[r - 1][i] = grid[r - 1][i + 1]
	}

	for i := r - 1; i > down; i-- {
		grid[i][c - 1] = grid[i - 1][c - 1]
	}

	for i := c - 1; i > 1; i-- {
		grid[down][i] = grid[down][i - 1]
	}

	grid[down][1] = 0
}

회고

단순한 시뮬레이션 구현 문제이지만, 배열을 탐색하는 것이 굉장히 헷갈리기 때문에 푸는데 오래걸렸습니다...