์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
- realm
- BOJ
- UIKit
- MVVM
- Swfit
- ํจ์คํธ์บ ํผ์ค
- CollectionView
- ํ๋ก๊ทธ๋๋จธ์ค
- RxSwift
- rxcocoa
- Lv2
- ๋ฐฑ์ค
- Flutter
- swift
- TCA
- BFS
- arkit
- tableView
- reactorkit
- XCTest
- raywenderlich
- SnapKit
- Xcode
- node.js
- SwiftUI
- designpattern
- combine
- ios
- Kuring
- visionOS
- Today
- Total
lgvv98
[Swift] BOJ 7576 ํ ๋งํ ๋ณธ๋ฌธ
BOJ 7576 ํ ๋งํ
โ ํ ๋งํ ๋ฌธ์ ๋ ์กฐ๊ธ ๋ ์๊ฐํด์ผ ํ์ผ๋ ๊ทธ๋๋ ์ด๋ ต์ง๋ ์์๋ค.
๋ค๋ง, ์๊ฐ์ด๊ณผ๋ฅผ ํด๊ฒฐํ์ง ๋ชปํด์ ๊ตฌ๊ธ๋ง์ ํ์๋๋ฐ, ์๋ฃ๊ตฌ์กฐ์ ๋ํ ์ดํด๋ ํ์คํ ์ค์ํ๋ค๊ณ ๋๋ ์๊ฐ์ด์๋ค.
โ ์๊ฐ์ด๊ณผ๊ฐ ๋๊ณ ๋๋ฆ ๊ฐ์ ํ์ฝ๋
queue์์ removeFirst()๋ฅผ ์ฌ์ฉํ๋ฉด O(N)์ด ๊ฑธ๋ฆฌ๋ index๋ก ์ฐธ์กฐํ๊ฒ๋ ์์
๊ทธ๋ฌ๋ ์๊ฐ์ด๊ณผ๋ ์ฌ์ ํ ๋๊ฐ์๋ค.
let n = readLine()!.components(separatedBy: " ").map { Int("\($0)")! }
var matrix = [[Int]](repeating: [Int](repeating: 0, count: n[0]), count: n[1])
var visited = [[Bool]](repeating: [Bool](repeating: false, count: n[0]), count: n[1])
var startIndexList = [[Int]]()
for i in 0..<n[1] {
let v = readLine()!.components(separatedBy: " ").map { Int("\($0)")! }
for j in 0..<v.count {
if v[j] == 1 {
startIndexList.append([i,j])
}
}
matrix[i] = v
}
// print(matrix)
// print(startIndexList)
// ์๊ธฐ์๋ฆฌ + ์ํ์ข์ฐ
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
// ์ฌ๋ฌ๊ฐ์ ํฌ์ธํธ๊ฐ ๋ฏธ๋ก์ฐพ๊ธฐ๋ฅผ ํด์ผํ๋ค.
var queue = startIndexList
visited[queue[0][0]][queue[0][1]] = true
// print("queue \(queue)")
var maxValue = 0
var queueIndex = 0 // ์๊ฐ๋ณต์ก๋ ๊ฐ์ ์ ์ํด์ ์ฌ์ฉ
while queue.count > queueIndex {
// print("queue.count \(queue.count) \(queueIndex)")
let x = queue[queueIndex][0]
let y = queue[queueIndex][1]
queueIndex += 1
for i in 0..<4 {
// ์ด๋ ๊ฐ๋ฅํ ์ขํ ๊ณ์ฐ
let nx = x + dx[i]
let ny = y + dy[i]
// ์ขํ๊ฐ board์ ์ขํ๋ฅผ ๋ฒ์ด๋์ง ์์ผ๋ฉด
if nx >= 0 && ny >= 0 && nx < n[1] && ny < n[0] && visited[nx][ny] == false {
if matrix[nx][ny] == 0 {
queue.append([nx, ny])
matrix[nx][ny] = matrix[x][y] + 1 // ์ด ์ด๋๊ฑฐ๋ฆฌ ๊ณ์ฐ
maxValue = matrix[nx][ny]
visited[nx][ny] = true // ๋ฐฉ๋ฌธํ ๊ณณ์ true๋ก ๋ณ๊ฒฝ
}
}
}
}
// print(matrix)
// var value = 0
var option = false
for list in matrix {
if list.contains(0) {
// print("list \(list)")
option = true
break
}
}
if !option {
print(maxValue-1)
} else {
print("-1")
}
โ ๊ฐ์ ํ์ฝ๋
์ ์ด๋ ์๊ณ ๋ฆฌ์ฆ์ด ํ๋ฆฌ์ง ์์๊ฑฐ ํ์คํ๋ค. ๋ฌธ์ ๋ฅผ ๋ฑ ๋ณด์์ ๋, ์ด์ ์ ํ์๋ ๋ฏธ๋ก ํ์๊ณผ ๋น์ทํ์๊ณ , queue์ read & write๋ฅผ ์ฌ์ฉํ์ง ์๊ณ ์ธ๋ฑ์ค๋ฅผ ์กฐ์ ํ์ฌ ์๊ฐ ๋ณต์ก๋์ ์ด๋์ ๊ฐ์ ธ๊ฐ๋ค.
๊ทธ๋ฐ๋ฐ ์๊ฐ์ด๊ณผ๋ก ๋ฌธ์ ๋ฅผ ํ ๊ธฐํ์กฐ์ฐจ ์์ด์ ๋ค๋ฅธ ๋ถ์ ์ฝ๋๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ๋ด ์ฝ๋๋ก (์ ๋ ฅ๋ถ, ๊ตฌํ๋ถ, ์ถ๋ ฅ๋ถ)๋ก ์ ํํ๋ฉด์ ์๋ํด ๋ณด์๋ค.
์ด ๋ฌธ์ ์ ํด๋ฒ์ ์์ฒญ ๊ฐ๋จํ๋ฐ, ๋ฏธ๋ก ํ์ ๋ฌธ์ ์์ ์ฒ์์ input์ ๋ฐ์ ๋ ์์์ ์ ์ฌ๋ฌ๊ฐ ๊ฐ์ง ์ ์์ผ๋ ๊ทธ ์์์ ๋ค์ ๊ทธ๋ฅ queue์ ์ฒ์์ ๋ฃ์ด์ฃผ๋ฉด ๋๋ค.
๊ทธ๋ฌ๋ฉด BFS์ ์ํด์ ํ์ํ๋ฉด์ ๊ณต๊ฐ์ ์ญ์ญ ์ฑ์๋๊ฐ๋๋ฐ, ์ด์ ๊ฐ์ ์์น์์ ์ด์ฐจํผ value๋ฅผ 1๋ํ๋ฏ๋ก ์ฝ๊ฒ ํด๊ฒฐํ ์ ์๋ค.
๋นจ๊ฐ ๊ธ์จ๊ฐ ์ ์ผ ํต์ฌ์ด๋๊น, ์กฐ๊ธ ๋ ์ค๋ช ์ ๋ง๋ถ์ด์๋ฉด
6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1
์๋ ๋ฐฑ์ค์ ๊ธฐ๋ณธ ํ ์คํธ ์ผ์ด์ค์ด๋ค.
์ด๊ธฐ ํ์๋ [(0,0), (3,5)]๊ฐ ์ ์ฅ๋๋ค.๊ทธ๋ฅ ๋ฏธ๋ก ํ์ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์งํํ๋ฉด ๊ฐ์ด ํ์์ ๊บผ๋ด๊ณ ๋ค์ ์์น๋ค์ ๊ฐ์ด 0์ด ์์ผ๋ฉด ๊ทธ ์์น๋ ํ์์ ๊บผ๋ธ ๊ฐ์ ์ธ๋ฑ์ค์ ์๋ ๊ฐ์์ 1์ ๋ํ๋ฉด ๋๋ค.์ฒ์์๋ (0,0)์ ๊บผ๋ด๊ณ (0,1) ์๋ฆฌ๋ง ๊ฐ์ด 2๋ก ๋ฐ๋๋ค. ๊ทธ๋ฆฌ๊ณ (0,1)์ queue์ ์ฝ์ ํ๋ค.
6 4
1 -1 0 0 0 0
2 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1
์ฒ์ ์ํํ๋ฉด ์์ ๊ฐ์ ๊ฒฐ๊ณผ๊ฐ ๋๊ณ queue์๋ [(3,5), (0,1)]์ด ๋ค์ด๊ฐ ์๋ค.
๋ค์ ํ์์ ๋ฝ์์ ๋ฏธ๋ก ํ์๊ณผ ๊ฐ์ ์๊ณ ๋ฆฌ์ฆ์ ์ํํ๋ฉด,
6 4
1 -1 0 0 0 0
2 -1 0 0 0 0
0 0 0 0 -1 2
0 0 0 0 -1 1
์์ ๊ฐ์ด ๋๊ณ , queue์๋ [(0,1), (2,4)]๊ฐ ๋ค์ด์๋ค.
๊ทธ๋ผ ์ด๋ ๊ฒ ์ญ์ญํ๋ค๊ฐ ์ด๋์ ๊ฐ ์ค๊ฐ์์ ๋ง๋๊ฒ ์ง?
๊ทผ๋ฐ ์ด์ฐจํผ 0์ด ์๋๋ฉด ์ ๊ฒฝ ์ธ ํ์๊ฐ ์์ด์ ์ด๋ ์ง์ ์์ ์ํ์ข์ฐ ๋ค ์ด๋ํ ์ ์์ด์ง๊ณ queue๋ฅผ ๋ค ์๋นํ๊ณ ๋๋๊ฒ ๋๋ค.
๋ค์ด ์๋ค๊ณ ํํํ์๋๋ฐ, ์ด ๊ฒฝ์ฐ์๋ ๋ฐฐ์ด์ ๊ฒฝ์ฐ์๋ O(N)์ ์๊ฐ๋ณต์ก๋๋ฅผ ์ํด๋ณด๊ฒ ๋์ด์ ๋๋ ์ด ๋ถ๋ถ์ queue์ index๋ก ์ฒ๋ฆฌํ๋ ๊ธฐ๋ฒ์ ์ฌ์ฉํ์๋ค.
โ ์ฝ๋
์ฝ๋๋ฅผ ๋น๊ตํด ๋ณธ ๊ฒฐ๊ณผ
* ์๊ฐ ์ด๊ณผ๊ฐ ๋ ๋ถ๋ถ : ์ ๋ ฅ๋ถ ์ ๋ ฅ๋ถ๋ฅผ ์๋ ์ฝ๋๋ก ๋ฐ๊พธ๋๊น ํด๊ฒฐ๋์์.๋ค๋ง, ๊ธฐ์กด ๋ด ์ฝ๋์ ์ด๋ค ๋ถ๋ถ์์ ์๊ฐ๋ณต์ก๋์์ ํฌ๊ฒ ์ํด๋ฅผ ๋ณด์๋์ง๋ ๋์ ํ ๋ชจ๋ฅด๊ฒ ์ ..
ํน์๋ผ๋ ๋๊ตฐ๊ฐ ์ด ๊ธ์ ๋ณด๊ณ ์์๋ ๋ถ ์์ผ์๋ฉด ์๋ ค์ฃผ์ธ์ ใ ใ
๋๋ ์๊ฐ ๋จ์ถ์ ํ๊ฒ ๋ค๊ณ visited๋ฅผ ์ฌ์ฉ ํ์๋๋ฐ, ์์ด๋ ๋ ๋น ๋ฅด๋ค๋
//https://www.acmicpc.net/problem/7576
import Foundation
struct b7576 {
static func run() {
let nums = readLine()!.split(separator: " ").map { Int($0)! }
let m = nums[0], n = nums[1]
var matrix = [[Int]]()
var queue = [(Int, Int)]()
for i in 0..<n {
let values = readLine()!.split(separator: " ").map { Int($0)! }
queue.append(contentsOf: values.enumerated().filter({ 1 == $0.element }).map { (i,$0.offset) }) // ๊ฐ์ด 1์ธ indexes
matrix.append(values)
}
//print(matrix)
// ์๊ธฐ์๋ฆฌ + ์ํ์ข์ฐ
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
// ์ฌ๋ฌ๊ฐ์ ํฌ์ธํธ๊ฐ ๋ฏธ๋ก์ฐพ๊ธฐ๋ฅผ ํด์ผํ๋ค.
var maxValue = 0
var queueIndex = 0 // ์๊ฐ๋ณต์ก๋ ๊ฐ์ ์ ์ํด์ ์ฌ์ฉ
while queue.count > queueIndex {
let x = queue[queueIndex].0
let y = queue[queueIndex].1
queueIndex += 1
for i in 0..<4 {
// ์ด๋ ๊ฐ๋ฅํ ์ขํ ๊ณ์ฐ
let nx = x + dx[i]
let ny = y + dy[i]
// ์ขํ๊ฐ board์ ์ขํ๋ฅผ ๋ฒ์ด๋์ง ์์ผ๋ฉด
if nx >= 0 && ny >= 0 && nx < n && ny < m {
if matrix[nx][ny] == 0 {
queue.append((nx, ny))
matrix[nx][ny] = matrix[x][y] + 1 // ์ด ์ด๋๊ฑฐ๋ฆฌ ๊ณ์ฐ
}
}
}
}
let flatvisited = matrix.flatMap { $0 }
maxValue = flatvisited.max() ?? 1
if flatvisited.contains(0) {
print("-1")
} else if maxValue == 1 {
print("0")
} else {
print(maxValue - 1)
}
}
}
(์ฐธ๊ณ )
2022.04.02 - [์ฝ๋ฉํ ์คํธ] - [Swift] BOJ 2178 ๋ฏธ๋ก ํ์
https://yurimac.tistory.com/48
'์ฝ๋ฉํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Swift] BOJ 11724 ์ฐ๊ฒฐ ์์์ ๊ฐ์ (0) | 2022.04.05 |
---|---|
[Swift] BOJ 1697 ์จ๋ฐ๊ผญ์ง (2์ฐจ์ ๋ฐฐ์ด๋ณด๋ค 1์ฐจ์ ํํ ๋ฐฐ์ด) (0) | 2022.04.05 |
[Swift] BOJ 2667 ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ (0) | 2022.04.03 |
[Swift] BOJ 1012 ์ ๊ธฐ๋ ๋ฐฐ์ถ (0) | 2022.04.03 |
[Swift] BOJ 2606 ๋ฐ์ด๋ฌ์ค (0) | 2022.04.03 |