[Swift Algorithm] 그림 BOJ #1926

문제 설명

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

 

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

 

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

 

입출력 예제

입력

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

출력

4
9

 

내 문제 풀이

import Foundation

let paper = readLine()!.split(separator: " ").map({Int(String($0))!}) // 주어진 도화지의 크기 (세로, 가로)
var check = [[Int]]() // 도화지 칸 별로 숫자 입력받는 배열

for _ in 0..<paper[0] {
    check.append(Array(readLine()!.split(separator: " ").map({Int(String($0))!})))
}

var count = 0 // 그림 개수 카운트
var area = 0 // 그림마다 넓이 체크
var max = 0 // 최대 그림 크기

// dfs 재귀함수
func solution(_ x: Int, _ y: Int) {
    if x < 0 || x >= paper[0] || y < 0 || y >= paper[1] || check[x][y] != 1 { return }
    
    check[x][y] = 0
    area += 1
    
    // 재귀 호출 (현재 자리와 붙어있는 주변 모든 자리 확인)
    solution(x+1, y) // 세로로 다음 자리
    solution(x-1, y) // 세로로 전 자리
    solution(x, y+1) // 가로로 다음 자리
    solution(x, y-1) // 가로로 전 자리
}

// 세로가 0 이상일 경우 코드 실행
if paper[0] > 0 {
    for i in 0..<paper[0] {
        for j in 0..<paper[1] {
            if check[i][j] == 1 {
                area = 0
                solution(i, j)
                count += 1 // 카운트
                if max < area { max = area }
            }
        }
    }
}

print(count) // 그림의 개수
print(max) // 최대 그림의 크기

👉 DFS 문제! 1로 채워진 모든 자리와, 그 자리와 이어진 모든 자리를 검사하는 것이 포인트!!

1이 있으면 그 자리 주변의 모든 자리를 검사하는 똑같은 수행을 계속 반복해야하므로 재귀함수로 풀이했다.

• 1) 우선 연산에 필요한 주요 변수 세 개를 선언해주었다.
  count는 답으로 출력해야하는 요소 중 하나로, 그림의 총 개수를 담을 예정!
  area는 재귀함수 안에서 1씩 더해가며 각 그림마다의 너비를 측정하기 위한 것.
  max는 count와 함께 답으로 출력할 요소로, 더 큰 area가 등장할 때마다 계속 업데이트!
• 2) DFS 재귀함수를 확인하기 전 아래의 메인 실행 코드를 먼저 확인해보자.
  2중 for문을 활용하여 모든 칸을 검사할 수 있도록 했고,
  검사하다가 해당 칸이 1일 경우 위에서 작성한 재귀함수를 실행하게 했다.
  (실행시키기 전에는 너비를 측정해줄 area 변수를 0으로 초기화했다.)
  그리고 1이 나왔다는건 적어도 크기가 1인 그림이 하나 있다는 뜻이므로 count에 1을 더해줬다.
  마지막으로 max보다, 방금 돌린 solution 함수가 구한 area가 더 크면 max를 업데이트했다.
• 3) 이제 solution 재귀함수의 실행 과정을 살펴보자.
  이 문제는 1로 채워진 자리들이 몇 개까지 이어져있는지를 체크해야한다.
  따라서 solution 함수 안에서 세로, 가로로 모든 방향으로 다시 solution 함수를 호출하여
  상하좌우의 자리가 1인지 0인지 체크해준다.
  체크하는 자리가 도화지의 범위를 넘어서거나 0일 경우는 if문을 이용해 예외로 빼주었고,
  그 외의 경우는 현재 체크완료한 자리를 0으로 변경해준 후 area에는 1을 더했다.
  (0으로 변경해준 이유는, 어차피 이어진 자리들은 하나의 그림이라 다시 검사할 필요가 없는데
  1로 그대로 놔두면 중복으로 계속 같은 그림을 검사하게 되니까.,,!!)

 

💡 피드백

• 처음 접한 DFS 문제라서 모든 자리를 검사해야하는줄 모르고
  이리저리 효율적인 방안을 생각해보다가 다른 분들 풀이를 검색해서 풀게됐는데,!
  모든 자리를 상하좌우로 꼼꼼히 살펴줘야하는구낭.,.
• 아직 DFS가 익숙하진 않아서 더 풀어봐야할듯.,!@

 

---

문제

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