프로그래머스 - Swift algorithm 0, 1 배열에서 1 덩어리 찾기

 

 

 

가로 세로 2차원 배열에서 "0"과 "1"을 배열하고

"1"이 가로세로 연결되었을 때 한 묶음으로 간주하여

총 몇 묶음인가, 또 가장 많은 "1"이 연결된 수를 구하는 문제다.

 

이런 식이다.

좌, 우 끝부터 보면 8개의 "1" 이 연결되어 있고

좌, 아래는 3개, 우, 상에는 3개, 우/하에는 10개의 "1"이

연결되어 있다.

결과는 총 4덩어리고 제일 큰 덩어리는 10개라서

정답은 4,10을 구하는 문제였다.

 

알고보니 DFS, BFS라는 알고리즘이다.

 

	// 문제 입력
	var maps : [[Int]] = [[1,1,0,1,1],[0,1,1,0,0],[0,0,0,0,0],[1,1,0,1,1],[1,0,1,1,1],[1,0,1,1,1]]
    print(DPS_algorithm(&maps))

	// 체크할 X,Y 방향 X[0],Y[0] 은 -1, 0 이므로 현재자리에서 X - 1 를 지정해준다.
    let X : [Int] = [-1,0,1,0]
    let Y : [Int] = [0,1,0,-1]
    var cnt : Int = 1
    

    func DPS_algorithm(_ maps:inout [[Int]]) -> [Int] {
    	// 결과 배열
        var arr : Array<Int> = Array()
        // 체크 했는지 여부 배열
        var check : [[Bool]] = [[Bool]](repeating:[Bool](repeating:false,count: maps[0].count),count: maps.count)
        for i in 0..<maps.count {
            for j in 0..<maps[i].count {
                if maps[i][j] == 1 {
                	// "1" 을 찾으면 dfs 를 돌리므로 cnt 는 1개로 시작
                    dfs(i,j,&check,&maps,&cnt)
                    arr.append(cnt)
                    cnt = 1
                } else {
                    continue
                }
            }
        }
        print(arr)
        return [1,2]
    }
    
    // 입력된 value 변경을 위해 inout를 붙여주고     
    func dfs(_ x:Int, _ y:Int, _ ck : inout [[Bool]],_ map : inout [[Int]], _ count : inout Int) {
        print("\(x) , \(y)")
        ck[x][y] = true
        map[x][y] = 0
        for i in 0..<4 {
            let nextX = x + X[i]
            let nextY = y + Y[i]
            if nextX < 0 || nextY < 0 || nextX >= ck.count || nextY >= ck[0].count {
                continue
            }
            if ck[nextX][nextY] {
                continue
            }
            if map[nextX][nextY] == 0 {
                ck[nextX][nextY] = true
                continue
            }
            if map[nextX][nextY] == 1 {
            	// 주변을 찾다가 "1" 다시 발견하면 재귀 호출
                count += 1
                dfs(nextX,nextY,&ck,&map,&count)
            }
        }
    }

 

프로그래머스, Codility 등 자신의 주력 언어를 선택하면

꼭 버전을 확인 하자

예> Swift 4.2 Linux