[BOJ] 백준 21736 헌내기는 친구가 필요해 (Swift)

문제

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

풀이

전형적인 그래프 문제이다.
BFS, DFS로 풀 수 있는 문제

문제 그대로 X 인 곳은 이동 불가능하고, DFS나 BFS로 탐색을 진행하면 쉽게 풀 수 있는 문제이다.

소스코드

	let dy = [1, 0, -1, 0]
	let dx = [0, 1, 0, -1]
	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let n = input[0], m = input[1]
	var graph: [[Character]] = []
	for _ in 0..<n { graph.append(readLine()!.map { $0 }) }
	var start = (0, 0)
	for y in 0..<n {
	for x in 0..<m {
	if graph[y][x] == "I" {
	start = (y, x)
	}
	}
	}
	var visited = [[Bool]](repeating: [Bool](repeating: false, count: m), count: n)
	var answer = 0
	func dfs(_ y: Int, _ x: Int) {
	visited[y][x] = true
	if graph[y][x] == "P" {
	answer += 1
	}
	for i in 0..<4 {
	let ny = y + dy[i]
	let nx = x + dx[i]
	if 0..<n ~= ny && 0..<m ~= nx && !visited[ny][nx] && graph[ny][nx] != "X" {
	visited[ny][nx] = true
	dfs(ny, nx)
	}
	}
	}
	dfs(start.0, start.1)
	print(answer == 0 ? "TT" : answer)

view raw 헌내기는 친구가 필요해.swift hosted with ❤ by GitHub

후기

그래프 탐색에 대한 이해가 있다면 쉽게 풀 수 있는 문제