[알고리즘/Swift] 1303 전쟁 - 전투
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 1303 전쟁 - 전투
- 제출 언어: Swift
- 알고리즘 분류:
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
- 깊이 우선 탐색
풀이
기본 BFS, DFS문제에 마지막 병사의 수를 제곱해서 더해주는 부분만 처리해주면 되는 문제였다
나는 visited 2차원 배열로 방문 여부를 파악하고
arr에 전쟁터에 있는 병사의 팀 상태를 입력해준다
func countSoldier(_ team: Character, _ x: Int, _ y: Int, _ count: inout Int) -> Int {
visited[x][y] = true
guard arr[x][y] == team else {return count}
for i in 0...3 {
if arr[x+dx[i]][y+dy[i]] == team && !visited[x+dx[i]][y+dy[i]]{
count += 1
countSoldier(team, x+dx[i], y+dy[i], &count)
}
}
return count
}
설계한 countSoldier
함수이다
- count하려는 팀원의 색상과, x좌표, y좌표, count를 입력받는다
- 방문한 전쟁터를 true로 바꿔준다
- 동서남북으로 전쟁터를 탐색해서 만약 탐색한 곳에 아군이 있지 않다면, count값을 return하고,
- 아군이 있다면 다시 동서남북으로 탐색을 한다 (이때, 재귀함수를 사용한다)
- 마지막으로 count값을 return한다
사용한 swift 문법
1. guard문
guard문을 통해 코드를 단순화하였다
//if문 사용
if arr[x][y] == team {
code~~
}
else {
return count
}
//guard문 사용
guard arr[x][y] == team else {return count}
code~~
2. inout 키워드 사용
함수를 선언할 때 파라미터앞에 inout 키워드를 붙인다
변수의 메모리 주소를 전달하는 것을 의미
var a = 1
var b = 2
func addAB(_ a :Int, _ b: Int) -> Int {
var temp = a
a = b //컴파일 에러 'a'는 상수임
b = temp //컴파일 에러 'b'는 상수임
}
addAB(a,b)
위의 경우는 전역변수의 값을 복사하여 함수의 인자로 보내지기 때문에 let으로 함수내에서 사용되고,
결국 그 값들은 변할 수 없다
var a = 1
var b = 2
func addAB(_ a :inout Int, _ b: inout Int) -> Int {
var temp = a
a = b
b = temp
return (a+b)
}
print(addAB(&a,&b))
위의 경우는 inout
키워드를 인자에 붙여 전역변수의 메모리 주소를 전달했으므로
값을 변경하면 전역변수의 값도 바뀐다
3. pow
두 수를 제곱하는 함수이다.
pow(Double, Double) -> Double
혹은 pow(Decimal, Int) -> Decimal
과 같은 형태로 제곱값을 반환한다
Decimal
은 생성자를 작성해줘야 하므로 밑과 지수 모두 Double
형태로 바꾸어 제곱을 계산하였다
func pow(
_ x: Decimal,
_ y: Int
) -> Decimal
func pow(
_ x: Double,
_ y: Double
) -> Double
전체 코드
import Foundation
let n = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N,M) = (n[0], n[1])
var arr: [[Character]] = Array(repeating: Array(repeating: " ", count: N+2), count: M+2)
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: N+2), count: M+2)
for i in 1...M {
arr[i][1...N] = ArraySlice(readLine()!)
}
let dx: [Int] = [1,-1,0,0] //동 서 남 북
let dy: [Int] = [0,0,1,-1]
var countBlue = 0
var countWhite = 0
func countSoldier(_ team: Character, _ x: Int, _ y: Int, _ count: inout Int) -> Int {
visited[x][y] = true
guard arr[x][y] == team else {return count}
for i in 0...3 {
if arr[x+dx[i]][y+dy[i]] == team && !visited[x+dx[i]][y+dy[i]]{
count += 1
countSoldier(team, x+dx[i], y+dy[i], &count)
}
}
return count
}
for i in 1...M {
for j in 1...N {
if !visited[i][j] {
var count = 1
let num = Int(pow(Double(countSoldier(arr[i][j], i, j, &count)), Double(2)))
if arr[i][j] == "B"{
countBlue += num
}
else{
countWhite += num
}
}
}
}
print(countWhite, countBlue)