훌이
후리스콜링개발
훌이

블로그 메뉴

  • 왈 (iOS APP)
  • Github
전체 방문자
오늘
어제
  • 전체 (171)
    • ⭐️ 개발 (140)
      • JAVA (4)
      • Web (5)
      • iOS & Swift (94)
      • iOS Concurrency (4)
      • Rx (18)
      • Git (6)
      • WWDC (1)
      • Code Refactor (3)
      • Server (1)
    • ⭐️ Computer Science (22)
      • 운영체제 (10)
      • 네트워크 (5)
      • PS (7)
    • 경제시사상식 (8)
    • 기타 등등 (0)

인기 글

최근 글

05-19 02:43

티스토리

hELLO · Designed By 정상우.
훌이
⭐️ Computer Science/PS

[PS] BOJ - 7576 토마토 골드5

[PS] BOJ - 7576 토마토 골드5
⭐️ Computer Science/PS

[PS] BOJ - 7576 토마토 골드5

2023. 3. 5. 23:02
728x90
반응형

처음에 파이썬으로 풀었던 문제라 swift로 바꾸는 것은 쉽지 않았는데 시간초과 문제가 발생했다.

파이썬은 큐 라이브러리를 제공해주는 점과 다르게 swift는 큐가 제공되지 않는데 그 과정에서 removeFirst를 쓰는 부분이 문제였다.

맨 앞 요소를 삭제하면 각 요소들이 하나씩 앞으로 이동하는데 그러면 시간복잡도가 O(n)으로 시간초과가 발생하게 된다.

 

그러면 어떻게 해야 하냐?

기존에 removeFirst를 통해서 가장 맨 앞 요소를 삭제하고 -> 인덱스가 하나씩 당겨졌을 것이다. 

이 대신에 index를 통해서 큐의 원소에 접근하는 방법을 사용하면 된다.

index는 0부터 시작이고, queue.count는 1부터 개수를 센다.

그래서 index가 더 커지는 while문을 벗어나는 방식으로 구현해주면 된다.

 

 

더불어, 새롭게 적용한 것 범위 연산자 ~=

0..<9 ~= n

n이 0이상 9미만의 범위에 포함되면 true, 아니면 false 반환

 

import Foundation

let mn = readLine()!.split(separator: " ").map { Int(String($0))! }
let m = mn[0]
let n = mn[1]
// 그래프 다시 그려줘야 돼
var graph = [[Int]]()
var visited = Array(repeating: Array(repeating: false, count: m), count: n)

for _ in 0..<n {
    graph.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

let dx = [1, -1, 0, 0]
let dy = [0, 0, 1, -1]

var answer = 0
var tomato = 0

var queue: [(Int, Int)] = []

for i in 0..<n {
    for j in 0..<m {
        // 그래프에 0이 없으면(안익은 토마토가 없으면) -> 0 출력
        if !graph[i].contains(0) {
            answer = 1 // 원래는 0을 출력하면 되는데 날짜개념상 첫 하루도 1일로 카운트되어서 1을 쳐줌
        } else { // 토마토 전체 개수를 구해~
            if graph[i][j] == 0 || graph[i][j] == 1 {
                tomato += 1
            }
            if graph[i][j] == 1 { // 좌표값이 1인 아이들의 x, y를 큐에 미리 넣어두기
                queue.append((i, j))
            }
        }
    }
}

var index = 0
// index가 queue.count보다 작을 때까지 돌려준다.
while index < queue.count {
    let newXY = queue[index]
    let x = newXY.0
    let y = newXY.1
    index += 1
    visited[x][y] = true

    for i in 0..<4 {
        let xx = x + dx[i]
        let yy = y + dy[i]
        
        if 0..<n ~= xx && 0..<m ~= yy {
            if !visited[xx][yy] && graph[xx][yy] == 0 {
                visited[xx][yy] = true
                graph[xx][yy] = graph[x][y] + 1
                queue.append((xx, yy))
                answer = graph[xx][yy]
            }
        }
    }
}

//# 모든 그래프 좌표 다 방문을 하면 False -> True로 방문처리가 될 것임
//# 그러면 그 뜻은 True인 것은 익은 토마토들이고, True 개수와 방문 전 1,0인 토마토 개수가 일치하는지 체크해줘야 함
//# 일치하면 다 방문했고, == 토마토가 다 익은 것임 // 일치하지 않으면 토마토가 익지 않은 게 있다는 뜻
var trueCount = 0
for i in 0..<n {
    for j in 0..<m {
        if visited[i][j] == true {
            trueCount += 1
        }
    }
}

if trueCount != tomato {
    print(-1)
} else {
    print(answer-1)
}
728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'⭐️ Computer Science > PS' 카테고리의 다른 글

[PS] 백트래킹 9663번 N-Queen 답지 참고  (0) 2023.04.24
[PS] 백트래킹 - n과m(11) (12), 부분수열의 합 1182  (0) 2023.04.22
[PS] 백트래킹 - n과m(9) 15663 어려움 시간초과 이슈 악  (0) 2023.04.19
[PS] 백트래킹 20문제 풀기 - 0. 개념, 1. n과m(1) ~ (4)  (0) 2023.04.17
[PS] 3/2 - BOJ 2644 촌수계산 - DFS  (0) 2023.03.02
    '⭐️ Computer Science/PS' 카테고리의 다른 글
    • [PS] 백트래킹 - n과m(11) (12), 부분수열의 합 1182
    • [PS] 백트래킹 - n과m(9) 15663 어려움 시간초과 이슈 악
    • [PS] 백트래킹 20문제 풀기 - 0. 개념, 1. n과m(1) ~ (4)
    • [PS] 3/2 - BOJ 2644 촌수계산 - DFS
    훌이
    훌이

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.