[백준] 1245번: 농장관리 Swift 풀이 (BFS/DFS)

2022. 12. 14. 02:19·Algorithm (PS)
목차
  1. 1. BFS 
  2. 2. DFS
728x90

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

 

1245번: 농장 관리

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수

www.acmicpc.net

 

swift 빠르다 빨라

 

1. BFS 

산봉우리들을 세는 문제이다. 좌표는 상하좌우 + 대각선, 총 8방향으로 인접한 칸이면 이동할 수 있으며, 높이 값이 0 이면 산봉우리가 아니다 !!! 따라서 bfs 탐색 또한 높이가 0 보다 클 때만 처리했다. 

bfs에서 , 현재 확인중인 array[x][y] 값을 중심으로, 자기자신 보다 높은 위치를 만나면 (x, y) 에 해당하는 봉우리 라인은 산봉우리가 될 수 없다. 

 if matrix[nx][ny] > matrix[x][y] { // 현재 탐색중인 값이 산봉우리가 아님
                    flag = false
                }

따라서 산봉우리 여부를 판단하는 변수인 flag에 false 값을 저장한다. 

if matrix[nx][ny] == matrix[x][y] && !visited[nx][ny]  { // 같은 높이의 산봉우리 탐색
                    visited[nx][ny] = true
                    queue.append([nx, ny])
                }

그리고 내가 bfs를 통해 하려는 작업은, 높이가 같으며 이어져있는 칸들을 방문하는 것이다. 
현재 높이보다 낮은 경우는 산봉우리를 찾는데 필요하지 않은 작업이므로, 이에 대해서 방문 여부를 처리하지 않았다. 

 

값을 처리하는 것은 여러 방법이 있겠지만, swift 특성상 전역변수 answer 를 하나 설정하고 산봉우리이면 그 값을 더해주는 방식으로 구했다. bfs 내의 파라미터로 넣으면 함수의 파라미터는 변수가 아닌 상수이므로 값을 바꿀수가 없다

 

import Foundation

let input = readLine()!.split { $0 == " "}.map{ Int(String($0))! }
let n = input[0]
let m = input[1]
var answer = 0
// reapting: 초기값, count: 배열의 크기
var matrix = Array(repeating: Array(repeating: 0, count: m), count: n)
for i in 0..<n {
    let data = readLine()!.split(separator: " ").map{ Int(String($0))! }
    matrix[i] = data
}

var visited = Array(repeating: Array(repeating: false, count: m), count: n)
// 8방향 탐색
let dx = [-1, 1, 0, 0, -1, 1, -1, 1]
let dy = [0, 0, -1, 1, -1, 1, 1, -1]


for i in 0..<n {
    for j in 0..<m {
        if matrix[i][j] > 0 && visited[i][j] == false {
            bfs(a: i, b: j)
        }
    }
}

func bfs(a:Int, b:Int) {
    answer += 1
    var flag = true
    var queue: [[Int]] = []
    queue.append([a, b])
    visited[a][b] = true

    while !queue.isEmpty {
        let d = queue.removeFirst()
        let x = d[0]
        let y = d[1]

        for i in 0..<8 {
            var nx = 0
            var ny = 0
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx && nx < n && 0 <= ny && ny < m { // 범위 내에 있는지 확인
                if matrix[nx][ny] > matrix[x][y] { // 현재 탐색중인 값이 산봉우리가 아님
                    flag = false
                }
                if matrix[nx][ny] == matrix[x][y] && !visited[nx][ny]  { // 같은 높이의 산봉우리 탐색
                    visited[nx][ny] = true
                    queue.append([nx, ny])
                }
            }
        }
    }
    
    // while 문 통과
    if flag == false {
        answer -= 1
    }
}
print(answer)

2. DFS

주요 로직은 동일하므로 설명은 생략하고 dfs로 푼 전체 코드이다. 

import Foundation

let input = readLine()!.split { $0 == " "}.map{ Int(String($0))! }
let n = input[0]
let m = input[1]
var answer = 0

var matrix = Array(repeating: Array(repeating: 0, count: m), count: n)
for i in 0..<n {
    let data = readLine()!.split(separator: " ").map{ Int(String($0))! }
    matrix[i] = data
}

var visited = Array(repeating: Array(repeating: false, count: m), count: n)
// 8방향 탐색
let dx = [-1, 1, 0, 0, -1, 1, -1, 1]
let dy = [0, 0, -1, 1, -1, 1, 1, -1]

var flag = true

for i in 0..<n {
    for j in 0..<m {
        if matrix[i][j] > 0 && visited[i][j] == false {
           // bfs(a: i, b: j)
            flag = true // reset flag to default
            dfs(x:i, y:j)
            if flag {
                answer += 1
            }
            
        }
    }
}

func dfs(x:Int, y:Int) {
    visited[x][y] = true
    for i in 0..<8 {
        let nx = x + dx[i]
        let ny = y + dy[i]
        if 0 <= nx && nx < n && 0 <= ny && ny < m {
            if matrix[nx][ny] > matrix[x][y] {
                flag = false
            }
            if matrix[nx][ny] == matrix[x][y] && visited[nx][ny] == false {
                dfs(x: nx, y: ny)
            }
        }
    }
}

print(answer)

 

 

728x90

'Algorithm (PS)' 카테고리의 다른 글

[백준] 12933번 : 오리 Swift 풀이 - 구현  (0) 2022.12.16
[프로그래머스] 행렬의 곱셈 Swift - 구현/선형대수학  (0) 2022.12.14
[백준] 10836번: 여왕벌 (파이썬/Python) - 시뮬레이션/구현/Greedy  (0) 2022.12.12
[백준] 14567번: 선수과목 (Python/파이썬) - 위상정렬  (0) 2022.12.11
[백준] 13913번 : 숨바꼭질 4 (파이썬/Python) - BFS 풀이  (0) 2022.12.10
  1. 1. BFS 
  2. 2. DFS
'Algorithm (PS)' 카테고리의 다른 글
  • [백준] 12933번 : 오리 Swift 풀이 - 구현
  • [프로그래머스] 행렬의 곱셈 Swift - 구현/선형대수학
  • [백준] 10836번: 여왕벌 (파이썬/Python) - 시뮬레이션/구현/Greedy
  • [백준] 14567번: 선수과목 (Python/파이썬) - 위상정렬
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (613)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (27)
      • Python (17)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (30)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (5)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • 카카오코딩테스트
  • 백트래킹
  • 데이터엔지니어
  • 파이썬
  • python
  • 클라우드
  • 빅데이터
  • SPARK
  • 리눅스
  • Leetcode
  • EC2
  • linux
  • 백준
  • 코딩테스트
  • docker
  • ansible
  • BFS
  • Swift
  • 프로그래머스
  • 데이터브릭스
  • 알고리즘
  • 쿠버네티스
  • dp
  • Kubernetes
  • 스파크
  • Databricks
  • dfs
  • 운영체제
  • AWS
  • 데이터엔지니어링

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[백준] 1245번: 농장관리 Swift 풀이 (BFS/DFS)
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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