문제 풀이를 할 때 마다 계속 추가됩니다.
cmd + F 를 통해 문제번호 찾기를 추천드립니다.
22.03.22 업데이트
22.03.25 업데이트
22.03.27 업데이트
22.03.28 업데이트
22.03.29 업데이트
22.03.30 업데이트
22.03.31 업데이트
22.04.03 업데이트
22.04.04 업데이트
22.04.13 업데이트
아래 깃허브 주소에서 모든 백준 문제풀이를 확인하실 수 있습니다.
https://github.com/SuminPark-developer/BaekJoonPS
GitHub - SuminPark-developer/BaekJoonPS: 백준 Swift PS
백준 Swift PS. Contribute to SuminPark-developer/BaekJoonPS development by creating an account on GitHub.
github.com
백준 Swift 17298번(시간초과)
// MARK: - 17298번(시간초과)
let N = Int(readLine()!)!
var nge: [Int] = [] // 오큰수 NGE 배열.
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
for i in 0..<N {
var flag: Bool = false
for j in i+1..<N {
if input[j] > input[i] { // 오큰수가 있으면,
nge.append(input[j])
flag = true
break // 가장 왼쪽(처음)나오는 수만 있으면 됨.
}
}
if !flag {
nge.append(-1)
}
}
for num in nge {
print(num, terminator: " ")
}백준 Swift 17298번(stack 사용)
// MARK: - 17298번(stack 사용)
let N = Int(readLine()!)!
var array = readLine()!.split(separator: " ").map{Int(String($0))!}
var stack: [Int] = [] // 오큰수가 아닌 수의 index를 저장.
for i in 0..<N {
while !stack.isEmpty && (array[stack.last!] < array[i]) {
array[stack.popLast()!] = array[i]
}
stack.append(i)
}
for index in stack { // 여전히 stack에 남아 있는 index는 오큰수 없음.
array[index] = -1
}
//for num in array { // 이렇게 출력하면 시간초과
// print(num, terminator: " ")
//}
print(array.map{String($0)}.joined(separator: " "))
백준 Swift 2696번
// MARK: - 2696번
let T = Int(readLine()!)!
for _ in 0..<T {
let M = Int(readLine()!)!
var numArray: [Int] = []
if M <= 10 {
numArray = readLine()!.split(separator: " ").map{Int(String($0))!}
}
else { // 11이상이면,
var line: Int = 0
if M % 10 == 0 {
line = M / 10
}
else {
line = M / 10 + 1
}
for _ in 0..<line {
numArray += readLine()!.split(separator: " ").map{Int(String($0))!}
}
}
var middleArray: [Int] = []
var tempArray: [Int] = []
for i in 0..<M {
tempArray.append(numArray[i])
if i % 2 == 0 { // 홀수번째 수일 때,
tempArray.sort(by: <)
middleArray.append(tempArray[(i+1)/2])
}
}
print(middleArray.count)
var answer = ""
for i in 0..<middleArray.count {
if (i != 0) && (i % 10 == 0) { // 첫번째 값 아니고, 10개씩 출력.
answer += "\n"
}
answer += String(middleArray[i]) + " "
}
print(answer)
}
백준 Swift 1715번
최소값 힙 사용 - 참고 : https://developer-p.tistory.com/196
// MARK: - 1715번 : https://developer-p.tistory.com/196
struct MinHeap<T: Comparable> {
var heap: [T] = []
var isEmpty: Bool {
return heap.count <= 1 ? true : false
}
init() {}
init(_ element: T) {
heap.append(element) // 0번 index채우기 용
heap.append(element) // 실제 Root Node 채움.
}
mutating func insert(_ element: T) {
if heap.isEmpty {
heap.append(element)
heap.append(element)
return
}
heap.append(element)
func isMoveUp(_ insertIndex: Int) -> Bool {
if insertIndex <= 1 { // Root Node일 때,
return false
}
let parentIndex = insertIndex / 2
return heap[insertIndex] < heap[parentIndex] ? true : false
}
var insertIndex = heap.count - 1
while isMoveUp(insertIndex) {
let parentIndex = insertIndex / 2
heap.swapAt(insertIndex, parentIndex)
insertIndex = parentIndex
}
}
enum moveDownStatus { case left, right, none }
mutating func pop() -> T? {
if heap.count <= 1 {
return nil
}
let returnData = heap[1]
heap.swapAt(1, heap.count - 1)
heap.removeLast()
func moveDown(_ poppedIndex: Int) -> moveDownStatus {
let leftChildIndex = poppedIndex * 2
let rightChildIndex = leftChildIndex + 1
// case1. 모든(왼쪽) 자식 노드가 없는 경우(완전이진트리는 왼쪽부터 채워지므로)
if leftChildIndex >= heap.count {
return .none
}
// case2. 왼쪽 자식 노드만 있는 경우
if rightChildIndex >= heap.count {
return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none
}
// case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
// case3-1. 자식들이 자신보다 모두 큰 경우(자신이 제일 작은 경우)
if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
return .none
}
// case3-2. 자식들이 자신보다 모두 작은 경우(왼쪽과 오른쪽 자식 중, 더 작은 자식을 선별)
if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
}
// case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 작은 경우
if (heap[leftChildIndex] < heap[poppedIndex]) || (heap[rightChildIndex] < heap[poppedIndex]) {
return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
}
return .none
}
var poppedIndex = 1
while true {
switch moveDown(poppedIndex) {
case .none:
return returnData
case .left:
let leftChildIndex = poppedIndex * 2
heap.swapAt(poppedIndex, leftChildIndex)
poppedIndex = leftChildIndex
case .right:
let rightChildIndex = (poppedIndex * 2) + 1
heap.swapAt(poppedIndex, rightChildIndex)
poppedIndex = rightChildIndex
}
}
}
}
let N = Int(readLine()!)!
var myMinHeap: MinHeap<Int> = MinHeap()
for _ in 0..<N {
let input = Int(readLine()!)!
myMinHeap.insert(input)
}
var result: Int = 0
for _ in 0..<N-1 {
let first = myMinHeap.pop()!
let second = myMinHeap.pop()!
let temp = first + second
result += temp
myMinHeap.insert(temp)
}
print(result)
백준 Swift 5397번
// MARK: - 5397번
let T = Int(readLine()!)!
for _ in 0..<T {
let input = readLine()!.map{String($0)}
var stack1: [String] = []
var stack2: [String] = []
for ch in input {
if ch == "<" {
if !stack1.isEmpty {
stack2.append(stack1.popLast()!)
}
}
else if ch == ">" {
if !stack2.isEmpty {
stack1.append(stack2.popLast()!)
}
}
else if ch == "-" {
if !stack1.isEmpty {
stack1.removeLast()
}
}
else { // 알파벳일 때,
stack1.append(ch)
}
}
let answer = stack1 + stack2.reversed()
print(answer.joined(separator: ""))
}
백준 Swift 10026번(DFS)
// MARK: - 10026번(DFS)
let N = Int(readLine()!)!
var board: [[String]] = []
var colorBoard = Array(repeating: Array(repeating: "", count: N), count: N)
var visited = Array(repeating: Array(repeating: false, count: N), count: N)
var count1: Int = 0
var count2: Int = 0
for _ in 0..<N {
let input = readLine()!.map{String($0)}
board.append(input)
}
for i in 0..<N {
for j in 0..<N {
if board[i][j] == "G" || board[i][j] == "R" {
colorBoard[i][j] = "R"
}
else {
colorBoard[i][j] = "B"
}
}
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < N)
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
// 적록색약이 아닌 사람
func dfs1(_ y: Int, _ x: Int) {
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) && !visited[ny][nx] && (board[y][x] == board[ny][nx]) {
visited[ny][nx] = true
dfs1(ny, nx)
}
}
}
for y in 0..<N {
for x in 0..<N {
if !visited[y][x] {
visited[y][x] = true
count1 += 1
dfs1(y, x)
}
}
}
// 적록색약인 사람
visited = Array(repeating: Array(repeating: false, count: N), count: N) // 방문기록 초기화.
func dfs2(_ y: Int, _ x: Int) {
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) && !visited[ny][nx] && ( colorBoard[y][x] == colorBoard[ny][nx]) {
visited[ny][nx] = true
dfs2(ny, nx)
}
}
}
for y in 0..<N {
for x in 0..<N {
if !visited[y][x] {
visited[y][x] = true
count2 += 1
dfs2(y, x)
}
}
}
print(count1, count2)백준 Swift 10026번(BFS)
// MARK: - 10026번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let N = Int(readLine()!)!
var board: [[String]] = []
var colorBoard = Array(repeating: Array(repeating: "", count: N), count: N)
var visited = Array(repeating: Array(repeating: false, count: N), count: N)
var count1: Int = 0
var count2: Int = 0
for _ in 0..<N {
let input = readLine()!.map{String($0)}
board.append(input)
}
for i in 0..<N {
for j in 0..<N {
if board[i][j] == "G" || board[i][j] == "R" {
colorBoard[i][j] = "R"
}
else {
colorBoard[i][j] = "B"
}
}
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < N)
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
// 적록색약이 아닌 사람
func bfs1(_ startY: Int, _ startX: Int) {
visited[startY][startX] = true
let q = Dequeue([(startY, startX)])
while !q.isEmpty {
let (y, x) = q.popFirst()
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) && !visited[ny][nx] && (board[y][x] == board[ny][nx]) {
visited[ny][nx] = true
q.pushLast((ny, nx))
}
}
}
}
for y in 0..<N {
for x in 0..<N {
if !visited[y][x] {
// visited[y][x] = true
count1 += 1
bfs1(y, x)
}
}
}
// 적록색약인 사람
visited = Array(repeating: Array(repeating: false, count: N), count: N) // 방문기록 초기화.
func bfs2(_ startY: Int, _ startX: Int) {
visited[startY][startX] = true
let q = Dequeue([(startY, startX)])
while !q.isEmpty {
let (y, x) = q.popFirst()
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) && !visited[ny][nx] && (colorBoard[y][x] == colorBoard[ny][nx]) {
visited[ny][nx] = true
q.pushLast((ny, nx))
}
}
}
}
for y in 0..<N {
for x in 0..<N {
if !visited[y][x] {
visited[y][x] = true
count2 += 1
bfs2(y, x)
}
}
}
print(count1, count2)
백준 Swift 6593번(BFS)
// MARK: - 6593번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
while true {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (L, R, C) = (input[0], input[1], input[2])
if (L == 0) && (R == 0) && (C == 0) {
break
}
var board = Array(repeating: Array(repeating: Array(repeating: "", count: C), count: R), count: L)
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: C), count: R), count: L)
for z in 0..<L {
for y in 0..<R {
let input = readLine()!.map{String($0)}
for x in 0..<C {
board[z][y][x] = input[x]
}
}
readLine()
}
func isValidCoord(_ z: Int, _ y: Int, _ x: Int) -> Bool {
return (0 <= z && z < L) && (0 <= y && y < R) && (0 <= x && x < C)
}
let dz = [0, 0, 0, 0, 1, -1]
let dy = [0, 1, 0, -1, 0 ,0]
let dx = [1, 0, -1, 0, 0, 0]
func bfs(_ startZ: Int, _ startY: Int, _ startX: Int) -> Int {
visited[startZ][startY][startX] = true
let q = Dequeue([(startZ, startY, startX, 0)])
while !q.isEmpty {
let (z, y, x, d) = q.popFirst()
for k in 0..<6 {
let nz = z + dz[k]
let ny = y + dy[k]
let nx = x + dx[k]
let nd = d + 1 // 이동 횟수(시간)
if isValidCoord(nz, ny, nx) && !visited[nz][ny][nx] && board[nz][ny][nx] == "." { // 통로면,
visited[nz][ny][nx] = true
q.pushLast((nz, ny, nx, nd))
}
else if isValidCoord(nz, ny, nx) && !visited[nz][ny][nx] && board[nz][ny][nx] == "E" { // 탈출통로면,
visited[nz][ny][nx] = true
return nd // 탈출 시간 return.
}
}
}
return -1 // 탈출 불가 시, -1 return. (Trapped!)
}
var time: Int = 0
outLoop: for z in 0..<L {
for y in 0..<R {
for x in 0..<C {
if !visited[z][y][x] && board[z][y][x] == "S" {
visited[z][y][x] = true
time = bfs(z, y, x)
break outLoop
}
}
}
}
if time == -1 {
print("Trapped!")
}
else {
print("Escaped in \(time) minute(s).")
}
}
백준 Swift 5427번(BFS)
// MARK: - 5427번(BFS)
class Dequeue<T> {
var enQueue: [T] = []
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let N = Int(readLine()!)!
for _ in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (w, h) = (input[0], input[1])
var board: [[String]] = []
var visited = Array(repeating: Array(repeating: -1, count: w), count: h)
var fireVisited = Array(repeating: Array(repeating: -1, count: w), count: h)
for _ in 0..<h {
let input = readLine()!.map{String($0)}
board.append(input)
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < h) && (0 <= x && x < w)
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1 ,0]
let fireQ: Dequeue<(Int, Int)> = Dequeue([])
func fireBfs() {
while !fireQ.isEmpty {
let (y, x) = fireQ.popFirst()
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) && (fireVisited[ny][nx] == -1) && board[ny][nx] != "#" { // 범위 안이고, 불이 방문한 적 없고, 벽이 아니면,
fireVisited[ny][nx] = fireVisited[y][x] + 1
fireQ.pushLast((ny, nx))
}
}
}
}
func bfs(_ startY: Int, _ startX: Int) -> Int {
let userQ = Dequeue([(startY, startX)])
// visited[startY][startX] = 0 // 사람 시작하는 곳 0으로 초기화.
while !userQ.isEmpty {
let (y, x) = userQ.popFirst()
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if (ny < 0 || ny >= h) || (nx < 0 || nx >= w) { // 탈출 성공 시,
return (visited[y][x] + 1)
}
if (visited[ny][nx] == -1) && (board[ny][nx] != "#") { // 사람이 방문한 적 없고, 벽이 아닐 때,
if (fireVisited[ny][nx] == -1) || (fireVisited[ny][nx] > visited[y][x] + 1) { // 불이 방문한 적 없거나, 불이 옮겨붙을 때 이동하면,
visited[ny][nx] = visited[y][x] + 1
userQ.pushLast((ny, nx))
}
}
}
}
return -100
}
var userStartY: Int = 0
var userStartX: Int = 0
for y in 0..<h {
for x in 0..<w {
if board[y][x] == "*" { // 불은 여러곳일 수 있음.
fireVisited[y][x] = 0 // 불 붙은 곳 0으로 초기화.
fireQ.pushLast((y, x))
}
else if board[y][x] == "@" { // 사람일 경우,
visited[y][x] = 0 // 사람 시작하는 곳 0으로 초기화.
(userStartY, userStartX) = (y, x)
}
}
}
fireBfs() // 불 먼저 붙임.
let answer = bfs(userStartY, userStartX) // 그 다음, 사람 움직이면서, 괜찮은지 체크.
if answer == -100 {
print("IMPOSSIBLE")
}
else {
print(answer)
}
}백준 Swift 5427번(BFS - index사용)
// MARK: - 5427번(BFS - Index 사용)
let N = Int(readLine()!)!
for _ in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (w, h) = (input[0], input[1])
var board: [[String]] = []
var visited = Array(repeating: Array(repeating: false, count: w), count: h)
var fireVisited = Array(repeating: Array(repeating: false, count: w), count: h)
for _ in 0..<h {
let input = readLine()!.map{String($0)}
board.append(input)
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < h) && (0 <= x && x < w)
}
func isEscape(_ y: Int, _ x: Int) -> Bool {
return (y == 0 || y == h - 1) || (x == 0 || x == w - 1)
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
var fireQ: [(Int, Int, Int)] = []
var userQ: [(Int, Int, Int)] = []
var isSuccessEscape: Bool = false
func bfs() -> Int {
var index: Int = 0
var fireIndex: Int = 0
var userIndex: Int = 0
while index < userQ.count && !isSuccessEscape {
index += 1
let fireCount = fireQ.count // fireQ의 카운트를 저장해서 호출해야 함. 그냥 while문에 fireQ.count를 쓰면, 계속 append되면서 오류 발생함.
while fireIndex < fireCount && !isSuccessEscape {
let (y, x, d) = fireQ[fireIndex]
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
let nd = d + 1
if isValidCoord(ny, nx) && !fireVisited[ny][nx] && board[ny][nx] != "#" {
fireVisited[ny][nx] = true
fireQ.append((ny, nx, nd))
}
}
fireIndex += 1
}
let userCount = userQ.count
while userIndex < userCount && !isSuccessEscape {
let (y, x, d) = userQ[userIndex]
if isEscape(y, x) { // 탈출 성공 시,
isSuccessEscape = true // 이 부분 없어도 됨.
return (d + 1)
}
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
let nd = d + 1
if isValidCoord(ny, nx) && !fireVisited[ny][nx] && !visited[ny][nx] && board[ny][nx] == "." {
visited[ny][nx] = true
userQ.append((ny, nx, nd))
}
}
userIndex += 1
}
}
return -1 // 탈출 실패 시,
}
for y in 0..<h {
for x in 0..<w {
if board[y][x] == "*" { // 불은 여러개일 수 있음.
fireQ.append((y, x, 0))
}
else if board[y][x] == "@" { // 사람일 때,
userQ.append((y, x, 0))
}
}
}
let answer = bfs()
answer != -1 ? print(answer) : print("IMPOSSIBLE")
}
백준 Swift 3055번
// MARK: - 3055번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (R, C) = (input[0], input[1])
var board: [[String]] = []
var visited = Array(repeating: Array(repeating: -1, count: C), count: R)
var waterVisited = Array(repeating: Array(repeating: -1, count: C), count: R)
for _ in 0..<R {
let input = readLine()!.map{String($0)}
board.append(input)
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < R) && (0 <= x && x < C)
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
let waterQ: Dequeue<(Int, Int)> = Dequeue([])
func waterBfs() {
while !waterQ.isEmpty {
let (y, x) = waterQ.popFirst()
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) && (waterVisited[ny][nx] == -1) && board[ny][nx] == "." { // 유효한 좌표 범위고, 물이 방문한 적이 없고, 통로면,
waterVisited[ny][nx] = waterVisited[y][x] + 1
waterQ.pushLast((ny, nx))
}
}
}
}
func userBfs(_ startY: Int, _ startX: Int) -> Int {
let userQ = Dequeue([(startY, startX)])
while !userQ.isEmpty {
let (y, x) = userQ.popFirst()
if board[y][x] == "D" { // 탈출 성공 시,
return visited[y][x]
}
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) && (visited[ny][nx] == -1) && board[ny][nx] != "X" { // 유효한 좌표 범위고, 사람이 방문한 적이 없고, 돌이 아닐 때,
if (waterVisited[ny][nx] == -1) || waterVisited[ny][nx] > visited[y][x] + 1 { // (물과 독립된 길이라) 물이 방문한 적이 없거나 or (물이 방문하기 전에) 고슴도치가 먼저 방문하면(고슴도치가 가고 물이 차오르는건 상관X),
visited[ny][nx] = visited[y][x] + 1
userQ.pushLast((ny, nx))
}
}
}
}
return -1 // 탈출 실패
}
var userStartY: Int = 0
var userStartX: Int = 0
for y in 0..<R {
for x in 0..<C {
if board[y][x] == "*" { // 물은 여러곳일 수 있음.
waterVisited[y][x] = 0
waterQ.pushLast((y, x))
}
else if board[y][x] == "S" { // 고슴도치면,
visited[y][x] = 0
(userStartY, userStartX) = (y, x)
}
}
}
waterBfs()
let answer = userBfs(userStartY, userStartX)
if answer == -1 {
print("KAKTUS")
}
else {
print(answer)
}
백준 Swift 2206번(BFS)
방문여부를 이렇게 기록해야 하는 이유 - https://www.acmicpc.net/board/view/67446
방문배열은 '모든 경우'를 나타낼 수 있어야 한다.
이 문제에서의 모든 경우는
'해당 위치에 벽을 부쉈던 상태로 이미 왔었거나, 해당 위치에 아직 벽을 부수지 않은 상태로 이미 왔었다.' 임.
이를 표현하기 위해 3차원 배열로 나타냄.
(위 링크의 설명글에서 인용)
풀이 참고 - http://t.ly/QiwU
// MARK: - 2206번(BFS)
// 참고) 방문여부를 이렇게 기록해야 하는 이유 - https://www.acmicpc.net/board/view/67446
// 참고) 풀이 참고 - https://velog.io/@aurora_97/%EB%B0%B1%EC%A4%80-2206%EB%B2%88-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-Swift
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var board: [[Int]] = []
var visited = Array(repeating: Array(repeating: [0, 0], count: M), count: N) // [0, 0]에서 - 왼쪽은 벽미사용 방문거리, 오른쪽은 벽사용 방문거리
for _ in 0..<N {
let input = readLine()!.map{Int(String($0))!}
board.append(input)
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < M)
}
func isEscape(_ y: Int, _ x: Int) -> Bool {
return (y == N - 1) && (x == M - 1)
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
func bfs(_ startY: Int, _ startX: Int) -> Int {
let q = Dequeue([(startY, startX, 0)]) // 0이면 벽 미사용, 1이면 벽 사용
visited[startY][startX][0] = 1 // 시작하는 칸도 포함.
while !q.isEmpty {
let (y, x, wall) = q.popFirst()
if isEscape(y, x) {
return (visited[y][x][wall])
}
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) {
if board[ny][nx] == 1 && wall == 0 { // 벽이 있고, 벽 미사용이면,
visited[ny][nx][1] = visited[y][x][0] + 1 // 벽 사용한 방문거리에 저장.
q.pushLast((ny, nx, 1))
}
else if board[ny][nx] == 0 && visited[ny][nx][wall] == 0 { // 길이고, (벽을 쓰고 or 안쓰고) 미방문일 때,
visited[ny][nx][wall] = visited[y][x][wall] + 1
q.pushLast((ny, nx, wall))
}
}
}
}
return -1
}
let answer = bfs(0, 0)
print(answer)
백준 Swift 14442번(BFS) - 18%에서 시간초과
// MARK: - 14442번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M, T) = (input[0], input[1], input[2]) // K -> T로 임의 변경.
var board: [[Int]] = []
var visited = Array(repeating: Array(repeating: Array(repeating: 0, count: T + 1), count: M), count: N)
for _ in 0..<N {
let input = readLine()!.map{Int(String($0))!}
board.append(input)
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < M)
}
func isEscape(_ y: Int, _ x: Int) -> Bool {
return (y == N - 1) && (x == M - 1)
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
func bfs(_ startY: Int, _ startX: Int) -> Int {
let q = Dequeue([(startY, startX, 0)])
visited[startY][startX][0] = 1 // 시작하는 칸 포함.
while !q.isEmpty {
let (y, x, wall) = q.popFirst()
if isEscape(y, x) {
return visited[y][x][wall]
}
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) {
if (board[ny][nx] == 1) && (wall < T) && (visited[ny][nx][wall+1] == 0) { // 벽이 있고, 벽뚫는사용회수가 T보다 적고, (벽+1)이 방문한 적이 없으면.
visited[ny][nx][wall + 1] = visited[y][x][wall] + 1 // wall +1 증가.
q.pushLast((ny, nx, wall + 1)) // 벽 사용회수 +1 증가.
}
else if board[ny][nx] == 0 && visited[ny][nx][wall] == 0 { // 벽이 없고, (벽을 사용했던 or 안했던 그에 맞게) 방문한 적이 없으면,
visited[ny][nx][wall] = visited[y][x][wall] + 1
q.pushLast((ny, nx, wall))
}
}
}
}
return -1
}
let answer = bfs(0, 0)
print(answer)index 사용코드 (똑같이 18%에서 시간초과.)
더보기
// MARK: - 14442번(BFS) - index 사용.
//class Dequeue<T> {
// var enQueue: [T]
// var deQueue: [T] = []
//
// var count: Int {
// return enQueue.count + deQueue.count
// }
//
// var isEmpty: Bool {
// return enQueue.isEmpty && deQueue.isEmpty
// }
//
// init(_ queue: [T]) {
// enQueue = queue
// }
//
// func pushLast(_ element: T) {
// enQueue.append(element)
// }
//
// func pushFirst(_ element: T) {
// deQueue.append(element)
// }
//
// func popLast() -> T {
// if enQueue.isEmpty {
// enQueue = deQueue.reversed()
// deQueue.removeAll()
// }
// return enQueue.popLast()!
// }
//
// func popFirst() -> T {
// if deQueue.isEmpty {
// deQueue = enQueue.reversed()
// enQueue.removeAll()
// }
// return deQueue.popLast()!
// }
//}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M, T) = (input[0], input[1], input[2]) // K -> T로 임의 변경.
var board: [[Int]] = []
var visited = Array(repeating: Array(repeating: Array(repeating: 0, count: T + 1), count: M), count: N)
for _ in 0..<N {
let input = readLine()!.map{Int(String($0))!}
board.append(input)
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < M)
}
func isEscape(_ y: Int, _ x: Int) -> Bool {
return (y == N - 1) && (x == M - 1)
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
func bfs(_ startY: Int, _ startX: Int) -> Int {
// let q = Dequeue([(startY, startX, 0)])
var q = [(startY, startX, 0)]
visited[startY][startX][0] = 1 // 시작하는 칸 포함.
var index: Int = 0
while index < q.count {
// let (y, x, wall) = q.popFirst()
let (y, x, wall) = q[index]
if isEscape(y, x) {
return visited[y][x][wall]
}
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) {
if (board[ny][nx] == 1) && (wall < T) && (visited[ny][nx][wall+1] == 0) { // 벽이 있고, 벽뚫는사용회수가 T보다 적고, (벽+1)이 방문한 적이 없으면.
visited[ny][nx][wall + 1] = visited[y][x][wall] + 1 // wall +1 증가.
// q.pushLast((ny, nx, wall + 1)) // 벽 사용회수 +1 증가.
q.append((ny, nx, wall + 1)) // 벽 사용회수 +1 증가.
}
else if board[ny][nx] == 0 && visited[ny][nx][wall] == 0 { // 벽이 없고, (벽을 사용했던 or 안했던 그에 맞게) 방문한 적이 없으면,
visited[ny][nx][wall] = visited[y][x][wall] + 1
// q.pushLast((ny, nx, wall))
q.append((ny, nx, wall))
}
}
}
index += 1
}
return -1
}
let answer = bfs(0, 0)
print(answer)
백준 Swift 7576번(BFS)
문제 유형 : BFS 최단거리 활용
난이도 : 골드5
// MARK: - 7576번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (M, N) = (input[0], input[1])
var board: [[Int]] = []
var visited = Array(repeating: Array(repeating: -1, count: M), count: N)
for _ in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
board.append(input)
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < M)
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1 ,0]
let q: Dequeue<(Int, Int)> = Dequeue([])
func bfs() {
while !q.isEmpty {
let (y, x) = q.popFirst()
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
if isValidCoord(ny, nx) && (visited[ny][nx] == -1) && board[ny][nx] == 0 { // 유효범위고, 방문한 적 없고, 익지 않은 토마토가 근처이면,
visited[ny][nx] = visited[y][x] + 1
q.pushLast((ny, nx))
}
}
}
}
for y in 0..<N {
for x in 0..<M {
if board[y][x] == 1 { // 익은 토마토 발견 시,
visited[y][x] = 0
q.pushLast((y, x))
}
else if board[y][x] == -1 { // 토마토가 없는 칸 발견 시, 접근 자체가 불가능.
visited[y][x] = -2 // 나중에 전체 토마토가 익었는지 체크를 위해, 미방문과 구분을 위해 -2로 둠.
}
}
}
bfs()
if visited.flatMap({$0}).contains(-1) { // 미방문한 토마토가 있으면,
print(-1)
}
else { // 모든 토마토가 익었다면,
print(visited.flatMap{$0}.max()!) // 최대값이 모두를 익게 하는 최소 일수임.
}
백준 Swift 5014번
문제 유형 : BFS 최단거리
난이도 : 골드5
// MARK: - 5014번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (F, S, G, U, D) = (input[0], input[1], input[2], input[3], input[4])
var board = Array(repeating: Array(repeating: 0, count: 1), count: F + 1) // (0층 제외) 1층부터 F층까지 생성.
var visited = Array(repeating: Array(repeating: -1, count: 1), count: F + 1) // (0층 제외) 1층부터 F층까지 생성.
board[0][0] = -1 // 0층은 제외.
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (1 <= y && y <= F) && (x == 0)
}
func isEscape(_ y: Int, _ x: Int) -> Bool {
return (y == G) && (x == 0) // 목표(G)층에 도달하면 탈출.
}
let dy = [U, (D * -1)] // 위나 아래로만 이동 가능.
func bfs(_ startY: Int, _ startX: Int) -> Int {
let q = Dequeue([(startY, startX)])
visited[startY][startX] = 0 // 시작부분 0으로 시작.
while !q.isEmpty {
let (y, x) = q.popFirst()
if isEscape(y, x) {
return visited[y][x]
}
for k in 0..<2 {
let ny = y + dy[k]
let nx = x // x는 계속 0
if isValidCoord(ny, nx) && board[ny][nx] == 0 && visited[ny][nx] == -1 { // 유효 범위고, (0층제외한) 1층부터 F층이고, 미방문이면,
visited[ny][nx] = visited[y][x] + 1
q.pushLast((ny, nx))
}
}
}
return -1
}
let answer = bfs(S, 0) // S층에서 시작.
answer == -1 ? print("use the stairs") : print(answer)
백준 Swift 12851번
문제 유형 : BFS - pop을 할 때 방문처리를 해 줘야, 같은 방문횟수level의 방문을 체크할 수 있음.
난이도 : 골드5
// MARK: - 12851번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var board = Array(repeating: 0, count: 100001) // 0부터 100000까지.
var visited = Array(repeating: false, count: 100001)
func isValidCoord(_ x: Int) -> Bool {
return (0 <= x && x <= 100000)
}
func isEscape(_ x: Int) -> Bool { // 수빈이를 만나면 탈출.
return (x == K)
}
var fastTimeArray: [Int] = []
func bfs(_ startX: Int) {
let q = Dequeue([(startX, 0)])
visited[startX] = true // 첫 시작 true로 초기화.
while !q.isEmpty {
let (x, d) = q.popFirst()
visited[x] = true // 숨바꼭질1과 다르게, 큐에서 pop할 때 방문처리해줘야 함.
if isEscape(x) { // 탈출 가능인데,
if fastTimeArray.isEmpty { // 처음이면,
fastTimeArray.append(d)
}
else { // 처음이 아닌데,
if d == fastTimeArray[0] { // 가장 빠른 시간과 같다면 방법 1개 증가.
fastTimeArray.append(d)
}
}
}
if isValidCoord(x + 1) && board[x + 1] == 0 && visited[x + 1] == false { // (x+1) - 유효 범위고, 방문할 수 있는 곳이고, 방문한 적 없으면,
q.pushLast((x+1, d+1))
}
if isValidCoord(x - 1) && board[x - 1] == 0 && visited[x - 1] == false { // (x-1) - 유효 범위고, 방문할 수 있는 곳이고, 방문한 적 없으면,
q.pushLast((x-1, d+1))
}
if isValidCoord(2 * x) && board[2 * x] == 0 && visited[2 * x] == false { // (2*x) - 유효 범위고, 방문할 수 있는 곳이고, 방문한 적 없으면,
q.pushLast((2*x, d+1))
}
}
}
bfs(N)
print(fastTimeArray.first!)
print(fastTimeArray.count)
백준 Swift 16397번
문제 유형 : BFS - 최단거리 : board는 필요 없었고, d(버튼 누른 횟수)가 T보다 작다는 조건이 추가로 필요했음.
난이도 : 골드4
// MARK: - 16397번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, T, G) = (input[0], input[1], input[2])
var visited = Array(repeating: false, count: 100000) // 0~99999 미방문 체크.
func isValidCoord(_ x: Int) -> Bool {
return (0 <= x && x <= 99999)
}
func isEscape(_ x: Int) -> Bool {
return (x == G)
}
func bfs(_ startX: Int) -> Int {
let q = Dequeue([(startX, 0)])
visited[startX] = true
while !q.isEmpty {
let (x, d) = q.popFirst()
if isEscape(x) {
return d
}
if isValidCoord(x + 1) && !visited[x + 1] && (d < T) { // 유효 범위고, 방문한 적 없고, 버튼 누른 회수가 T회 미만이면,
visited[x + 1] = true
q.pushLast((x + 1, d + 1))
}
if isValidCoord(2 * x) { // 2배한 숫자가 유효 범위고,
var temp = String(2 * x).map{String($0)}
for i in 0..<temp.count {
if temp[i] != "0" {
temp[i] = String(Int(temp[i])! - 1)
break
}
}
let pressB = Int(temp.reduce("", +))! // B를 누른 결과 숫자.
if !visited[pressB] && (d < T) { // B를 누른 결과의 숫자에 방문한 적 없고, 버튼 누른 회수가 T회 미만이면,
visited[pressB] = true
q.pushLast((pressB, d + 1))
}
}
}
return -1
}
let answer = bfs(N)
answer == -1 ? print("ANG") : print(answer)
백준 Swift 9019번
문제 유형 : BFS인데, 시간초과로 애를 먹었다.
런타임 에러 : 처음에 (n == 0)이 아니라 (n-1 == 0)으로 잘못했었는데, 이 부분만 문제인 줄 알았다. (이 외에, 시간초과를 유발하는 많은 이유가 있었다.)
예상 시간 초과 원인 1. : 직접 만든 Dequeue 클래스를 써서, 기존의 배열(q)보단 빠를 것으로 예상되나, (덱의) q.popFirst() 혹은 q.removeFirst()에서 많은 시간이 쓰이는 것 같았다.
예상 시간 초과 원인 2. : 원인1을 해결하기 위해, index를 도입해 데이터를 접근하는 식으로 변경했으나 여전히 타임 오버.
예상 시간 초과 원인 3. : String d를 둬서 각각의 결과(문자)를 이어 붙이는 과정에서, 많은 질문글을 찾아보니 String이 시간초과를 유발한다고 함. (물론 Swift로 된 질문은 없었...다...ㅠㅠ)
[여담으로, 원인3은 사실 할 말이 많다. 타 블로그에 올라와 있는 C언어나 파이썬으로 된 코드들은 원인3을 해결하지 않아도, 기존에 했던 방식처럼 (d + "S") 이런식으로 해도 문제 없이 통과 되는데, Swift의 상대적으로 느린 속도는 문제다... 추가시간을 달라! 슬프군..]
참고 링크 : https://www.acmicpc.net/board/view/54644 | https://www.acmicpc.net/source/40983157
난이도 : 골드4
// MARK: - 9019번(BFS) - 시간초과 개선
let T = Int(readLine()!)!
for _ in 0..<T {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (A, B) = (input[0], input[1])
var visited = Array(repeating: false, count: 10000)
func bfs(_ startX: Int) -> String {
var q: [(Int, Int)] = [(startX, 0)] // (Int, String)으로 하면 시간초과.
visited[startX] = true
var index: Int = 0
var answer: String = ""
while index < q.count {
let (x, d) = q[index] // d는 원래는 String으로 이어붙이는 식으로 했었는데, 그렇게 하면 시간초과나서 Int로 계산해주고, 마지막에 이어붙이는 식으로 함.
if x == B { // B에 도달하면,
for ch in String(d) {
switch ch {
case "1":
answer += "D"
case "2":
answer += "S"
case "3":
answer += "L"
case "4":
answer += "R"
default:
break
}
}
return answer // 명령어(answer) 반환.
}
if x*2 > 9999 { // D일 때, - 9999보다 큰 경우.
let temp = x*2 % 10000
if !visited[temp] {
visited[temp] = true
q.append((temp, d * 10 + 1))
}
}
else { // D일 때, - 9999이하인 경우.
if !visited[x*2] {
visited[x*2] = true
q.append((x*2, d * 10 + 1))
}
}
if x == 0 { // S일 때, - n이 0인 경우. ( x-1이 0일때가 아니라, x가 0일 때임.)
let temp = 9999
if !visited[temp] {
visited[temp] = true
q.append((temp, d * 10 + 2))
}
}
else { // S일 때, - n이 0이 아닌 경우.
if !visited[x-1] {
visited[x-1] = true
q.append((x-1, d * 10 + 2))
}
}
// L 부분.
let lFront = x % 1000
let lBack = x / 1000
let lNum = (lFront * 10) + lBack // L을 사용시 나오는 숫자.
if !visited[lNum] {
visited[lNum] = true
q.append((lNum, d * 10 + 3))
}
// R 부분.
let rFront = x % 10
let rBack = x / 10
let rNum = (rFront * 1000) + rBack // R을 사용시 나오는 숫자.
if !visited[rNum] {
visited[rNum] = true
q.append((rNum, d * 10 + 4))
}
index += 1
}
return "no" // 여기 오는 일은 없음.
}
let answer = bfs(A)
print(answer)
}
백준 Swift 1525번
문제 유형 : BFS활용
- BFS의 처음보는 활용이었다. 그 동안은 배열을 이용해 bfs를 풀어왔는데, board배열의 값을 매번 바꿔줘야 하는 점에서 풀이를 생각하지 못했다.
상하좌우 모두 방문하면서, 그 때 마다 board를 바꿔주면, 그 다음부턴 망가져버리기 때문이다. ( 매 방문마다의 배열을 저장할 수도 없는 노릇이니...)
결국엔 다른 사람의 풀이를 참고해서 풀게 됐다.
board를 2차원배열이 아닌 [String]으로 처리해서 시간을 단축시키고, Set으로 방문처리를 해서 시간단축을 하는게 중요했다.
방문처리를 만약 배열로 했다면 contains체크시 O(N)이 걸린다. 하지만 Set의 .contains는 시간복잡도가 O(1)이기 때문에, 큰 시간단축이 됐다.
(https://stackoverflow.com/questions/46385749/swift-3-array-contains-vs-set-contains | https://stackoverflow.com/questions/50240554/swift-set-contains-complexity)
(다른 언어의 풀이들에선 String으로 하던데, Swift는 String을 다루긴 힘들어서 배열String으로 처리했다. 그냥 String은 인덱스 접근이 뭔가 어렵다. 쉽게 하는 방법 아시는 분 있으면 댓글달아주세요...)
난이도 : 골드2
참고 링크 : https://2hs-rti.tistory.com/78
// MARK: - 1525번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let target = "123456780"
var board: [String] = []
var visited: Set<[String]> = []
for _ in 0..<3 {
let input = readLine()!.split(separator: " ").map{String($0)}
board.append(input[0])
board.append(input[1])
board.append(input[2])
}
var startY: Int = 0
var startX: Int = 0
for (index, ch) in board.enumerated() {
if ch == "0" {
startY = index / 3
startX = index % 3
break
}
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < 3) && (0 <= x && x < 3)
}
func isEscape(_ arr: [String]) -> Bool {
return arr.reduce("", +) == target
}
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
func bfs(_ startY: Int, _ startX: Int) -> Int {
let q = Dequeue([(startY, startX, 0, board)])
visited.insert(board)
while !q.isEmpty {
var (y, x, d, strArray) = q.popFirst()
// print("\(y), \(x), \(d), \(visited)")
if isEscape(strArray) {
return d
}
for k in 0..<4 {
let ny = y + dy[k]
let nx = x + dx[k]
let nd = d + 1
if isValidCoord(ny, nx) { // 유효한 범위이면서,
let index = y * 3 + x
let nextIndex = ny * 3 + nx
let temp = strArray[index] // swap.
strArray[index] = strArray[nextIndex]
strArray[nextIndex] = temp
if !visited.contains(strArray) { // 방문한 적 없으면,
visited.insert(strArray)
q.pushLast((ny, nx, nd, strArray))
}
strArray[nextIndex] = strArray[index] // strArray를 망가뜨리면 안되기 때문에 다시 재swap.
strArray[index] = temp
}
}
}
return -1
}
let answer = bfs(startY, startX)
print(answer)
백준 Swift 1039번
문제 유형 : BFS 활용
핵심 : 전체 숫자들의 방문체크가 아닌, 각 순차적으로 증가하는 K(depth)일 때의 숫자들의 방문체크를 해야 한다.
- 처음엔 방문체크를 While문 안에 Set<[String]> 으로 했었다. 전역변수로 방문체크를 하면 안되고, 그 depth에 해당하는 숫자들의 방문체크를 해줘야 했기 때문이다.
내가 짠 코드는 근데 그렇게 하면 K-1번째꺼 까지의 방문체크는 되는데, K번째일 때의 방문체크가 안되는 것이다! 😂 이거때문에 계속 고민하고... 근데 결국 못함. (메모리 초과) [이 방법 참고 글 : https://gusdnr69.tistory.com/266]
결국 이 방법으로는 해결하지 못하고, 2차원배열로 방문체크를 하는 방법으로 해결했다.
참고로 index를 활용한 Ver1이 조금 더 빠르다. (근데 난 큐의 isEmpty를 쓰는게 더 편하다.. Ver2)
난이도 : 골드3
참고 링크 : https://vapor3965.tistory.com/36
Ver1.
// MARK: - 1039번(BFS)
let input = readLine()!.split(separator: " ").map{String($0)}
let (N, K) = (input[0].map{String($0)}, Int(input[1])!)
var visited = Array(repeating: Array(repeating: false, count: 1000001), count: 11) // 각 depth일 때의 방문체크가 필요함.
//var maxAnswer: Int = 0
var answerArray: [Int] = [] // depth가 K번째일 때의 정답숫자들 모음.
func bfs(_ startX: [String]) {
var q: [([String], Int)] = [(startX, 0)]
var index: Int = 0
while index < q.count {
let (x, d) = q[index]
index += 1 // 그 depth에 해당하는 값들을 비교해야 하기 때문에, index증가부분이 밑이 아니라 여기있어야 함.
if d == K { // K번째일 때,
answerArray.append(Int(x.reduce("", +))!)
// maxAnswer = max(maxAnswer, Int(x.reduce("", +))!)
continue // d가 K번째일 때꺼까지만 필요하고, 더 이상 진행하면 X.
}
for i in 0..<N.count {
for j in i+1..<N.count {
var swapTemp: [String] = x // x의 스왑을 위한 임시변수.
swapTemp.swapAt(i, j)
let swapNum = Int(swapTemp.reduce("", +))!
if swapTemp[0] != "0" && !visited[d][swapNum] {
visited[d][swapNum] = true
q.append((swapTemp, d + 1))
}
}
}
}
}
bfs(N)
answerArray.isEmpty ? print("-1") : print(answerArray.max()!)Ver 2.
: 늘 쓰던 큐의 isEmpty를 쓰는 버전.
(index 쓰는 Ver1이 조금 더 빠르다.)
// MARK: - 1039번(BFS) - index 말고 큐 isEmpty쓰는 버전.
let input = readLine()!.split(separator: " ").map{String($0)}
let (N, K) = (input[0].map{String($0)}, Int(input[1])!)
var visited = Array(repeating: Array(repeating: false, count: 1000001), count: 11) // 각 depth일 때의 방문체크가 필요함.
//var maxAnswer: Int = 0
var answerArray: [Int] = [] // depth가 K번째일 때의 정답숫자들 모음.
func bfs(_ startX: [String]) {
var q: [([String], Int)] = [(startX, 0)]
// var index: Int = 0
while !q.isEmpty {
let (x, d) = q.removeFirst()
// index += 1 // 그 depth에 해당하는 값들을 비교해야 하기 때문에, index증가부분이 밑이 아니라 여기있어야 함.
if d == K { // K번째일 때,
answerArray.append(Int(x.reduce("", +))!)
// maxAnswer = max(maxAnswer, Int(x.reduce("", +))!)
continue // d가 K번째일 때꺼까지만 필요하고, 더 이상 진행하면 X.
}
for i in 0..<N.count {
for j in i+1..<N.count {
var swapTemp: [String] = x // x의 스왑을 위한 임시변수.
swapTemp.swapAt(i, j)
let swapNum = Int(swapTemp.reduce("", +))!
if swapTemp[0] != "0" && !visited[d][swapNum] {
visited[d][swapNum] = true
q.append((swapTemp, d + 1))
}
}
}
}
}
bfs(N)
answerArray.isEmpty ? print("-1") : print(answerArray.max()!)백준 Swift 2412번
문제 유형 : BFS 활용
- 처음 문제를 보고 BFS문제라는건 파악했다. 최소로 하면서 정상에 올라야 한다는 건, 최단거리라는 뜻이기 때문이다.
처음 풀이는 시간초과가 났다. steps배열을 매번 처음부터 돌면서, visited배열을 체크해서 그런 것 같다.
다른 블로그의 풀이를 참고해보니, steps를 set로 하면, (홈들의 위치를 받아놓고,) 방문 시 지워주기만 하면 방문체크를 따로 하지 않아도 됐다.
또한 abs(~~)계산을 매번 하게 짜지 않고, dy와 dx로 접근하는 방법을 생각하지 못한 게 아쉬웠다. (비슷한 문제가 나왔을 때 다음부턴 이 방법을 생각하자!)
난이도 : 골드3
참고 링크 : https://t.ly/cf8A
// MARK: - 2412번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
self.enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, T) = (input[0], input[1])
//var steps: [(y: Int, x: Int)] = []
var steps: Set<[Int]> = []
var maxTemp: Int = -1
for _ in 0..<n {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (y, x) = (input[1], input[0])
steps.insert([y, x])
maxTemp = max(maxTemp, x)
}
//print(steps)
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y <= T) && (0 <= x && x <= maxTemp)
}
func isEscape(_ y: Int) -> Bool {
return (y == T) // 정상 도달
}
let dy = [-2, -1, 0, 1, 2]
let dx = [-2, -1, 0, 1, 2]
func bfs(_ startY: Int, _ startX: Int) -> Int {
// var q: [(Int, Int, Int)] = [(startY, startX, 0)]
let q = Dequeue([(startY, startX, 0)])
// visited[startY][startX] = true
while !q.isEmpty {
let (y, x, d) = q.popFirst()
if isEscape(y) {
return d
}
for k in 0..<5 { // -2 <= y <= 2
for v in 0..<5 { // -2 <= x <= 2
let ny = y + dy[k]
let nx = x + dx[v]
let nd = d + 1
if isValidCoord(ny, nx) && steps.contains([ny, nx]) { // 유효 범위고, 그 자리에 홈이 있으면,
steps.remove([ny, nx]) // 홈 방문 했으니, 지움. (=얘가 방문체크를 대체함.)
q.pushLast((ny, nx, nd))
}
}
}
}
return -1
}
let answer = bfs(0, 0)
print(answer)시간 초과 코드
더보기
시간 초과 코드
// MARK: - 2412번(BFS)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
self.enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, T) = (input[0], input[1])
var steps: [(x: Int, y: Int)] = []
var maxTemp: Int = -1
for _ in 0..<n {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (x, y) = (input[0], input[1])
steps.append((x, y))
maxTemp = max(maxTemp, x)
}
steps.sort(by: <)
//print(steps)
var visited = Array(repeating: Array(repeating: false, count: maxTemp + 1), count: T + 1)
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y <= T) && (0 <= x && x <= maxTemp)
}
func isEscape(_ y: Int) -> Bool {
return (y == T) // 정상 도달
}
func bfs(_ startY: Int, _ startX: Int) -> Int {
// var q: [(Int, Int, Int)] = [(startY, startX, 0)]
let q = Dequeue([(startY, startX, 0)])
visited[startY][startX] = true
while !q.isEmpty {
let (y, x, d) = q.popFirst()
if isEscape(y) {
return d
}
for k in 0..<steps.count {
let ny = steps[k].y
let nx = steps[k].x
let nd = d + 1
if isValidCoord(ny, nx) && !visited[ny][nx] && (abs(ny - y) <= 2) && (abs(nx - x) <= 2) {
visited[ny][nx] = true
// q.append((ny, nx, nd))
q.pushLast((ny, nx, nd))
}
}
}
return -1
}
let answer = bfs(0, 0)
print(answer)
반응형
최근댓글