백준 - 1138.바닥장식

문제

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.

기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M의 제한은 100이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1 복사

4 4
----
----
----
----

예제 출력 1 복사

4

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

풀이

알고리즘 분류의 BFS 또는 DFS로 풀어본다.

들어오는 바닥 모양을 2차원 배열에 넣어서 상하,좌우를 확인하고,

모양이 이어지면 하나로 카운팅한다.

현재 검색하는 위치를 0로 바꾸어서 탐색 했음을 체크해둔다. 그리고 상하좌우 확인 시 0인 부분은 탐색하지 않고 현재 위치와 같은 모양의 바닥의 경우에만 카운팅 하도록 한다.

var nm = ""
var n = 0
var floor = [[String]]()
var count = 0
let dirX = [-1,1,0,0] // 상하좌우
let dirY = [0,0,-1,1]

func main() -> Int {
    nm = readLine()!
    n = Int(String((nm.first)!))!

    if nm == "0 0" { // n과 m이 0일 때는 0을 출력하도록 예외처리
        return 0
    }
    for _ in 1 ... n {
        let line = readLine()!.map{String($0)}
        floor.append(line)
    }
    for i in 0 ..< floor.count {
        for j in 0 ..< floor[0].count {
            if floor[i][j] == "-" || floor[i][j] == "|" {
                count += 1
                bfs(x: i, y: j)
            }
        }
    }
    return count
}
print(main())

func bfs(x: Int, y: Int) {
    var xy = (x,y) // 현재 확인 하고 있는 위치를 저장

    // 상하좌우 모두 확인하여 카운팅 하도록 큐 배열을 만들어 둔다
    var q = [(Int,Int)]() 

    // 현재 확인 중인 위치의 모양을 저장
    let value = floor[x][y]

    q.append((x,y))

    while !q.isEmpty {
        xy = q[0]

      // 현재 확인 중인 위치는 지워주고 0으로 바꿔준다,
        q.removeFirst()
        floor[xy.0][xy.1] = "0"

        if value == "-" {
            for i in 2 ... 3 {
              // 현재 위치의 좌우를 확인한다.
                let nx = xy.0 + dirX[i] // 0,0
                let ny = xy.1 + dirY[i] // -1,1

                if (ny >= 0 && ny < floor[0].count) &&
                   floor[nx][ny] != "0" && floor[nx][ny] == "-" {
                    q.append((nx,ny))
                }
            }
        }

        if value == "|" {
            for i in 0 ... 1 {
              // 현재 위치의 상하를 확인한다.
                let nx = xy.0 + dirX[i]
                let ny = xy.1 + dirY[i]

                if (nx >= 0 && nx < floor.count) &&
                   floor[nx][ny] != "0" && floor[nx][ny] == "|" {
                    q.append((nx,ny))
                }
            }
        }
    }
}

다만... 이렇게 제출하면 틀린다고 나오는데.... 어디가 틀린건지 모르겠다... 테스트케이스로 돌려보면 전부 맞게 나온다.....ㅠ
혹시 어디가 틀린지 아시면 피드백 부탁드려요!!