글 읽기 - [Swift] BFS로 풀어봤는데 틀린부분이 있을까요?

whdvy3 2년 전 0

논리가 틀린부분이 있을까요?

저는 BFS를 탐색하면서 X가 있으면 그 X주변을 검사해서

주변에 X가 있고 그 X가 방문한적이 있는곳이라면, 그곳은 색칠한 곳으로 판단해서 카운트를 올려서 아래 코드와같이 구현하였습니다.

let n = Int(String(readLine()!))!
var arr = [[String]]()

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

let checkX = [0, 0, -1, 1, -1, 1]
let checkY = [-1, 1, 0, 0, -1, 1]
for _ in 0..<n{
    arr.append(readLine()!.map{String($0)})
}
var result = 0
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
func check(_ x: Int, _ y: Int){
    var cnt = 0
    for i in 0..<6{
        let nx = x + checkX[i]
        let ny = y + checkY[i]
        if nx < 0 || nx >= n || ny < 0 || ny >= n {continue}
        
        if arr[nx][ny] == "X" && visited[nx][ny] {
            cnt += 1
        }
    }
    if cnt == 0 {
        result = max(result, 1)
    }else if cnt == 1{
        result = max(result, 2)
    }else{
        result = max(result, 3)
    }
}
func bfs(){
    var queue = [(Int, Int)]()
    queue.append((n - 1,0))
    visited[n - 1][0] = true
    
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        let x = pop.0
        let y = pop.1
        if arr[x][y] == "X"{
            check(x, y)
        }
        
        for i in 0..<2{
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]{continue}
            visited[nx][ny] = true
            queue.append((nx, ny))
        }
        
        
    }
}
bfs()
print(result)

wapas 2년 전 1

반례입니다.

# data input
3
-X-
-XX
X--

# program output
3

# correct answer
2

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Swift] BFS로 풀어봤는데 틀린부분이 있을까요?

whdvy3 2년 전 0

wapas 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말