[14466] 소가 길을 건너간 이유 6

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

14466번: 소가 길을 건너간 이유 6

그래프 탐색과 조합론으로 접근했다.

 

풀이

기본적인 그래프 탐색 문제와의 차별점은 지나가면 안 되는 간선이 주어진다는 점이다. 해당 부분을 어떻게 저장하고 핸들링할지 고민해하는 것이 이번 문제의 핵심.

 

인접행렬은 상, 하, 좌, 우로 4방향을 따져야 하므로 map[x좌표][y좌표][넘어갈 수 있는 방향 정보] 형태의 3차원 배열을 생성하였다. 즉 N*N*4 배열을 통해 너비우선탐색을 수행하여 해당 소가 방문하지 못하는 좌표에 다른 소가 있다면 문제에서 요구하는 답으로 판정하였다.

 

문제에서 요구하는 것은 길을 통해 건너야만 만날 수 있는 '쌍'을 찾는 것이니 중복을 없애기 위해 K에서 2개를 뽑는 조합 반복문을 통해 그래프탐색을 수행하였다.

 

정답 코드

	import Foundation
	let line = readLine()!.split(separator: " ").map{Int($0)!}
	let N = line[0]
	let K = line[1]
	let R = line[2]
	var map = Array(repeating: Array(repeating: Array(repeating: true, count: 4), count: N), count: N)
	var visited = Array(repeating: Array(repeating: false, count: N), count: N)
	var cows = [(Int,Int)]()
	let dx = [-1,1,0,0]
	let dy = [0,0,-1,1]
	var ans = 0
	func bfs(x:Int, y:Int){
	var q = [(x,y)]
	var idx = 0
	visited[x][y] = true
	while idx < q.count{
	let curr = q[idx]
	let x = curr.0
	let y = curr.1
	for i in 0..<4{
	let nx = x + dx[i]
	let ny = y + dy[i]
	if !map[x][y][i] || nx<0 || nx>=N || ny<0 || ny>=N{ continue }
	if !visited[nx][ny]{
	visited[nx][ny] = true
	q.append((nx,ny))
	}
	}
	idx += 1
	}
	}
	for _ in 0..<R{
	let line = readLine()!.split(separator: " ").map{Int($0)!-1}
	let ux = line[0]
	let uy = line[1]
	let vx = line[2]
	let vy = line[3]
	for i in 0..<4{
	let nx = ux + dx[i]
	let ny = uy + dy[i]
	if nx == vx && ny == vy{
	map[ux][uy][i] = false
	}
	}
	for i in 0..<4{
	let nx = vx + dx[i]
	let ny = vy + dy[i]
	if nx == ux && ny == uy{
	map[vx][vy][i] = false
	}
	}
	}
	for _ in 0..<K{
	let line = readLine()!.split(separator: " ").map{Int($0)!-1}
	cows.append((line[0],line[1]))
	}
	for i in 0..<K-1{
	let curr = cows[i]
	visited = Array(repeating: Array(repeating: false, count: N), count: N)
	bfs(x: curr.0, y: curr.1)
	for p in i+1..<K{
	let next = cows[p]
	if !visited[next.0][next.1]{
	ans += 1
	}
	}
	}
	print(ans)

view raw 14466.swift hosted with ❤ by GitHub