[2638] 치즈

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

2638번: 치즈

그래프 탐색 문제다.

 

풀이

모눈종이의 가장자리에는 치즈가 없다. 즉 (0,0) 좌표부터 너비우선탐색을 수행하여 치즈를 마주치면 해당 좌표를 저장. 탐색도중 같은 좌표를 한번 더 마주하게 된다면 해당 치즈는 2변이 실내온도에 닿은 것으로 판정하여 녹은 것으로 판정한다. 좌표를 저장하고 탐색하는 데에 O(1)만에 탐색이 가능한 Set 자료구조를 사용하였다. 치즈의 개수가 0이 될 때까지 탐색을 수행. 반복이 일어난 횟수를 출력하면 된다.

 

정답 코드

	import Foundation
	let nm = readLine()!.split(separator: " ").map{Int($0)!}
	let N = nm[0]
	let M = nm[1]
	var cheeze = 0
	var map = Array(repeating: Array(repeating: 0, count: M), count: N)
	for i in 0..<N{
	let line = readLine()!.split(separator: " ").map{Int($0)!}
	for k in 0..<M{
	if line[k] == 1{
	map[i][k] = 1
	cheeze += 1
	}
	}
	}
	func melting(){
	var set = Set<[Int]>()
	var visited = Array(repeating: Array(repeating: false, count: M), count: N)
	visited[0][0] = true
	let dx = [1,-1,0,0]
	let dy = [0,0,-1,1]
	var q = [(x:0,y:0)]
	var idx = 0
	while idx < q.count{
	let curr = q[idx]
	for i in 0..<4{
	let nx = curr.x + dx[i]
	let ny = curr.y + dy[i]
	if nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny]{ continue }
	if map[nx][ny] == 0{
	visited[nx][ny] = true
	q.append((nx,ny))
	}else{
	if set.contains([nx,ny]){
	map[nx][ny] = 0
	visited[nx][ny] = true
	cheeze -= 1
	}else{
	set.insert([nx,ny])
	}
	}
	}
	idx += 1
	}
	}
	var count = 0
	while cheeze > 0{
	count += 1
	melting()
	}
	print(count)

view raw 2638.swift hosted with ❤ by GitHub