[BOJ] 백준 9205 맥주 마시면서 걸어가기 (Swift)

문제

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

9205번: 맥주 마시면서 걸어가기

풀이

BFS로 풀이할 수 있는 문제입니다.
입력으로 x, y 좌표를 주기 때문에 방향을 사용하여 풀이해야 하나 헷갈릴 수 있지만 그렇지 않습니다.

단순히 상근이네 집에서 락 페스티벌의 좌표로 이동할 수 있는지 확인하는 것에 중점을 두어야 합니다.
상근이네 집, 편의점, 락 페스티벌의 좌표를 노드라고 생각하고, 노드 사이 거리가 1,000 이하라면 연결되어 있다고 생각합시다.

1,000 이하라면 노드간에 이동할 수 있으므로, 연결시켜주고
상근이네 집에서 어떠한 경로든 상관없이 락 페스티벌의 좌표로 이동할 수 있다면 happy, 못한다면 sad를 출력시켜줍시다.

소스코드

	func solution() {
	let n = Int(readLine()!)!
	let house = readLine()!.split(separator: " ").map { Int($0)! }
	var graph = [[Int]](repeating: [], count: n + 2)
	var visited = [Bool](repeating: false, count: n + 2)
	var edges = [house]
	for _ in 0..<n {
	edges.append(readLine()!.split(separator: " ").map { Int($0)! })
	}
	let end = readLine()!.split(separator: " ").map { Int($0)! }
	edges.append(end)
	for i in 0..<n + 1 {
	for j in i + 1..<n + 2 {
	if abs(edges[i][0] - edges[j][0]) + abs(edges[i][1] - edges[j][1]) <= 1_000 {
	graph[i].append(j)
	graph[j].append(i)
	}
	}
	}
	var queue = [0]
	var index = 0
	var answer = "sad"
	while queue.count > index {
	let current = queue[index]
	visited[current] = true
	if current == n + 1 {
	answer = "happy"
	break
	}
	for next in graph[current] {
	if !visited[next] {
	visited[next] = true
	queue.append(next)
	}
	}
	index += 1
	}
	print(answer)
	}
	let t = Int(readLine()!)!
	for _ in 0..<t { solution() }

view raw 맥주 마시면서 걸어가기.swift hosted with ❤ by GitHub

후기

방향을 기준으로 이동하는 것을 먼저 떠올렸지만, 직접 그래프를 만들어 주어야 했던 문제였습니다.