[Swift][BFS] 백준 16928번 (뱀과 사다리 게임)

요구능력 : 요구조건에 따른 BFS를 잘 설계할 수 있는지

 

코드설명 : 

 

이 문제는 기본적인 BFS를 이해하고 있으면 간단하게 풀릴것 같지만 조건을 아주 잘 지켜줘야 정답에 통과가된다.

 

우선 나는 튜플을 이용해서 (현재있는위치, 이동횟수)를 큐에 삽입하는 방식으로 문제를 해결했다.

다른 블로그들보면 딕셔너리 많이 사용하던데 나는 그냥 각각 2차원 배열에 사다리[x, y]와 뱀의 위치[u, v]를 넣어줬다.

 

그리고 BFS를 통해서 처음시작위치가 1이고 이동횟수는 0이기 때문에 큐에 (1,0)을 넣어주었다.

방문처리도 꼼꼼히 해준다.

 

그리고 형식적인 BFS의 공식..?같은 느낌으로다가 큐가 비어있지않으면 계속해서 while문을 돌려준다.

그리고 큐니까 맨앞에서 뽑아온다.(pop에 저장)

 

문제가 100에 도착했을때 최소경로니까 100에 도착하면 100에 도착했을 때 이동횟수를 프린트해주고 while문을 빠져나온다.

 

이 문제의 조건을 한번 살펴보자.

1. 주사위 던졌을때 나온 수를 더했을 때 100이 넘으면 이동안한다.

2. 도착한 칸이 사다리면 사다리타고 올라간다.

3. 도착한 칸이 뱀이면 뱀타고 내려간다.

 

참고 : 아래 코드에서 pop.0은 현재칸임

 

어차피 1~6까지 주사위굴려서 방문하는건 똑같기 때문에 for문으로 돌려준다.

for문 아래 첫번째 if문이다. 현재위치에서 주사위 굴려서 나온 수(i)를 더했을 때 100보다 작거나같아야한다. 그리고 방문하지 않았어야한다.(최단경로니까)

if pop.0 + i <= 100 && !visited[pop.0 + i]{}

 

사다리칸인지 뱀칸인지 확인하는 부분이다.

내가 이 문제를 22%에서 계속 틀린 부분이 있는데 바로 조건에서 사다리타고 가는도착지와 뱀타고 가는부분의 도착지의 방문여부를 확인해서였다.

내가 생각한 방문여부 확인하면 안되는이유 2가지

1. 방문했던 안했던 결국 해당하는 곳에 도착하면 사다리를 탈수밖에없는데 방문처리되있다고 사다리 안탈수는 없다.

2.방문했던 안했던 어차피 지름길이라 타는게 맞다.

그렇게 현재위치 + 주사위굴린값이 사다리위치랑 같으면 큐에넣고 방문체크해준다

 

isChecked는 내가 사다리타거나 뱀타면 현재위치 + 주사위굴린값 을 방문안하기위해서 넣어주었다.

내가 이 문제를 여러번틀린 이유중에 하나이다.

현재위치 + 주사위굴린값에 가서 뱀타고 내려갔는데

현재위치 + 주사위굴린값을 방문해버리면 뱀타고 내려간게 아닌게된다.

예를들어서 현재위치가 90이다. 주사위굴려서 2가나와서 92로 이동했는데 거기가 뱀위치다.

뱀 따라서 80까지 내려간다.

근데 만약에 92를 방문처리하고 큐에 넣어버리면 뱀타고 내려간게 아닌게된다.

for j in 0..<n{
  if nArr[j][0] == pop.0 + i{
    queue.append((nArr[j][1], pop.1 + 1))
    visited[nArr[j][1]] = true
    isChecked = false
  	}
  }
  for j in 0..<m{
    if mArr[j][0] == pop.0 + i{
      queue.append((mArr[j][1], pop.1 + 1))
      visited[mArr[j][1]] = true
      isChecked = false
  	}
  }

 

 

후기 : 조건에 대한 해석능력이 뛰어나야하는 문제같다.. BFS로 접근해서 풀이는 금방했는데 조건 2가지를 못지켜줘서 문제를 계속틀린..

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0] //사다리의 수
let m = nm[1] // 뱀의 수

var nArr = [[Int]]()
var mArr = [[Int]]()
var queue = [(Int, Int)]()
var visited = Array(repeating: false, count: 101)
var isChecked = true
for _ in 0..<n{
    nArr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

for _ in 0..<m{
    mArr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

func bfs(){
    queue.append((1,0))
    visited[1] = true
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if pop.0 == 100{
            print(pop.1)
            break
        }


        for i in 1...6{
            if pop.0 + i <= 100 && !visited[pop.0 + i] {
                for j in 0..<n{
                    if nArr[j][0] == pop.0 + i{
                        queue.append((nArr[j][1], pop.1 + 1))
                        visited[nArr[j][1]] = true
                        isChecked = false
                    }
                }
                for j in 0..<m{
                    if mArr[j][0] == pop.0 + i{
                        queue.append((mArr[j][1], pop.1 + 1))
                        visited[mArr[j][1]] = true
                        isChecked = false
                    }
                }
                
                if isChecked{
                    queue.append((pop.0 + i, pop.1 + 1))
                    visited[pop.0 + i] = true
                }
            }
            isChecked = true
        }
        
    }
}

bfs()

---

추후에 문제를 다시풀어봤을 때는 훨씬 쉽게 풀었습니다.

사다리와 뱀을 따로 받지않았습니다.

따로 받을 필요없이 도착하면 이동해야되기 때문입니다.

 

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]

var arr = [[Int]]()
for _ in 0..<n + m{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}


func bfs(){
    var visited = Array(repeating: false, count: 101)
    var queue = [(Int, Int)]()//현재위치, 주사위굴린 횟수
        
    queue.append((1, 0))
    visited[1] = true
    var idx = 0
    while queue.count > idx{
        let pop = queue[idx]
        idx += 1
        var curLocation = pop.0
        
        if curLocation == 100{
            print(pop.1)
            break
        }
        for i in arr{
            if i[0] == pop.0{
                curLocation = i[1]
            }
        }
        for i in 1...6{
            let move = curLocation + i
            if move > 100 || visited[move] {continue}
            queue.append((move, pop.1 + 1))
            visited[move] = true
        }
        
    }
}
                    
bfs()