[BOJ] 백준 4963 섬의 개수 (Swift)

문제

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

4963번: 섬의 개수

풀이

• 딱 보자마자 길찾기 문제다! 라고 생각했음
• 동, 남, 서, 북, 대각선(4방향)을 고려해야겠다고 생각함
• DFS/BFS 둘 다로 풀이할 수 있을 것 같다고 느낌

소스코드

	// 동 남 서 북 대각선 4방향
	let dx = [1, 0, -1, 0, 1, 1, -1, -1]
	let dy = [0, 1, 0, -1, -1, 1, -1, 1]
	while true {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	// 종료조건
	if input == [0, 0] {
	break
	}
	let w = input[0], h = input[1]
	var graph: [[Int]] = []
	for _ in 0..<h {
	graph.append(readLine()!.split(separator: " ").map { Int($0)! })
	}
	// 방문여부를 알 수 있는 배열
	var visited = [[Bool]](repeating: [Bool](repeating: false, count: w), count: h)
	// 섬의 범위를 벗어날 수 있는지
	func isVaildCoord(y: Int, x: Int) -> Bool {
	return 0..<h ~= y && 0..<w ~= x
	}
	// BFS 함수
	func bfs(y: Int, x: Int) {
	var queue = [(y: y, x: x)]
	var index = 0
	visited[y][x] = true
	// 큐처럼 동작하도록 구현
	// removeFirst()는 O(n)이기 때문에 index를 늘리고 접근하는 방식으로 O(1)로 구현할 수 있음
	while queue.count > index {
	let coord = queue[index]
	let y = coord.y
	let x = coord.x
	for i in 0..<8 {
	let ny = y + dy[i]
	let nx = x + dx[i]
	if isVaildCoord(y: ny, x: nx) && !visited[ny][nx] && graph[ny][nx] == 1 {
	visited[ny][nx] = true
	queue.append((ny, nx))
	}
	}
	index += 1
	}
	}
	var answer = 0
	for y in 0..<h {
	for x in 0..<w {
	if graph[y][x] == 1 && !visited[y][x] {
	answer += 1
	bfs(y: y, x: x)
	}
	}
	}
	print(answer)
	}

view raw 섬의 개수(BFS).swift hosted with ❤ by GitHub

	// 동 남 서 북 대각선 4방향
	let dx = [1, 0, -1, 0, 1, 1, -1, -1]
	let dy = [0, 1, 0, -1, -1, 1, -1, 1]
	while true {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	// 종료조건
	if input == [0, 0] {
	break
	}
	let w = input[0], h = input[1]
	var graph: [[Int]] = []
	for _ in 0..<h {
	graph.append(readLine()!.split(separator: " ").map { Int($0)! })
	}
	// 방문여부를 알 수 있는 배열
	var visited = [[Bool]](repeating: [Bool](repeating: false, count: w), count: h)
	// 섬의 범위를 벗어날 수 있는지
	func isVaildCoord(y: Int, x: Int) -> Bool {
	return 0..<h ~= y && 0..<w ~= x
	}
	// DFS 함수
	func dfs(y: Int, x: Int) {
	visited[y][x] = true
	for i in 0..<8 {
	let ny = y + dy[i]
	let nx = x + dx[i]
	if isVaildCoord(y: ny, x: nx) && !visited[ny][nx] && graph[ny][nx] == 1 {
	dfs(y: ny, x: nx)
	}
	}
	}
	var answer = 0
	for y in 0..<h {
	for x in 0..<w {
	if graph[y][x] == 1 && !visited[y][x] {
	answer += 1
	dfs(y: y, x: x)
	}
	}
	}
	print(answer)
	}

view raw 섬의 개수(DFS).swift hosted with ❤ by GitHub

후기

많은 그래프 문제들과 같이 연결 요소의 갯수를 구하는 문제라고 생각한다.

다만 방향이 8가지란 점에서 dx, dy를 8개로 정의를 해줘야 했던 문제였다.

그 외에는 기본적인 BFS/DFS 문제였다고 생각한다.