요구능력 : BFS의 방향성 활용
코드설명 :
이 문제는 얍문님의 블로그를 참고하였습니다.
너무 잘 설명해주신다..
참고 : https://yabmoons.tistory.com/125
[ 백준 6087 ] 레이저 통신 (C++)
백준의 레이저통신(6087) 문제이다. ( 문제 바로가기 ) [ 문제풀이 ] 1) 먼저 문제를 풀기전에 주의해야 할 점에 대해서 생각해보자. 우리는 이 문제를 풀 때, 방향이 꺾이는 과정일 때 무언가를
yabmoons.tistory.com
문제의 핵심
1. 설치해야하는 거울 개수의 최소값을 구해야하므로 BFS를 생각할 수 있다.
2. C로 표시되어있는 두 칸을 사용해야하므로 C로표시되어있는 두 칸을 구해야한다.
3. 4방향으로 탐색해야한다.
4. 거울을 설치해서 방향을 90도 회전 시킬 수 있으므로 진행방향을 고려해줘야한다.
2. C로 표시되어있는 두 칸을 사용해야하므로 C로표시되어있는 두 칸을 구해야한다.
C로 표시된 2칸을 사용해야하기 때문에 배열에 저장해줬다.
C 2개를 레이저로 연결한다는 말은 결국 C 1개의 위치에서 시작해서 다른 C를 찾는다는 말과 같은말이다.
다른 C를 찾을 때 방해가 될 수 있으니 시작할 C를 .으로 바꿔준다.(안전빵)
for i in 0..<h{
arr.append(readLine()!.map{$0})
for j in 0..<w{
if arr[i][j] == "C"{
cLocation.append(i)
cLocation.append(j)
}
}
}
arr[cLocation[0]][cLocation[1]] = "."
3. 4방향으로 탐색해야한다.
4. 거울을 설치해서 방향을 90도 회전 시킬 수 있으므로 진행방향을 고려해줘야한다.
visited를 bool형태로 초기화하지않고 Int.max로 초기화한 이유는 여기에 거울의 최소개수를 담을것이기 때문이다.
처음에 큐에 시작하는 방향별 진행방향을 넣어준다.
이유는 한쪽만 추가해주게되면 한쪽방향의 큐만 빼게됬을 때 나머지 방향으로 갈때 방향이 1씩 추가된다. 반대편방향으로 가면 2가 추가될것이다.(거울을 2번써서 움직여야하기때문) 아래 그림같은 느낌이다.
그래서 처음에 4방향 모두 큐에 추가해줘야한다.
그리고 더이상 진행할 큐가 없을때 까지 bfs()를 실행해주는데,,
나는 여기서 큰 실수를 하나 했었다.
mirrorCnt를 미래 진행방향이라고 적어놓은 for문안에서 값을 변경한것이다.
그렇게되면 4방향 도는동안 값이 계속 누적되게되서 정답이 절대로 안나온다..
그 다음 현재 뽑은 큐의 진행방향과 미래 진행방향을 비교해서 같지 않으면 거울개수를 하나 추가해준다.
여기서 나는 궁금한점이 있었다.
내가 정의해놓은 dx dy(동,서,남,북)에 의하면 인덱스 0과 1은 좌우방향이고 2와 3은 수직방향인데,,
direct(현재 큐의방향)가 0이고 미래 진행방향이 1이면 180도라서 거울이 필요없어서 같이 처리해줘도 되는게아닌가..?
생각도 할 필요 없었다.
그냥 다른 방향으로 인식시키고 만약 현재진행방향이 0이고 미래 진행방향이 1이라면 동 -> 서로 가는건데 +1을 하면 어차피 진행방향이 동이고 서쪽으로 한칸이동하면 이미 지나왔던 칸일것이고 그 칸은 최소값을 적용하기 때문에 서-> 동으로 인해서 생기는 + 1이 적용되지 않는다.
그리고 마지막으로
저장되어있는 거울개수가 현재 구한 거울개수보다 많으면 교체를 진행해주고 큐에 추가해준다.
func bfs(){
var visited = Array(repeating: Array(repeating: Int.max, count: 10001), count: 10001)
var queue = [( (Int, Int), Int, Int )]() //x, y, 현재 큐의 진행방향, 거울개수
for i in 0..<4{
queue.append(((cLocation[0], cLocation[1]),i ,0))
}
visited[cLocation[0]][cLocation[1]] = 0
var idx = 0
while queue.count > idx {
let pop = queue[idx]
let x = pop.0.0
let y = pop.0.1
let direct = pop.1
let mirrorCnt = pop.2
idx += 1
for i in 0..<4{ //미래 진행방향
let nx = x + dx[i]
let ny = y + dy[i]
var nCnt = mirrorCnt
if nx < 0 || nx >= h || ny < 0 || ny >= w || arr[nx][ny] == "*"{continue}
if direct != i{
nCnt += 1
}
if visited[nx][ny] >= nCnt {
visited[nx][ny] = nCnt
queue.append(((nx, ny), i, nCnt))
}
}
}
print(visited[cLocation[2]][cLocation[3]])
}
후기 : 너무 많이 헤맸다.. 내게는 너무 어려웠던문제....
let wh = readLine()!.split(separator: " ").map{Int(String($0))!}
let w = wh[0]
let h = wh[1]
var arr = [[Character]]()
let dx = [0, 0, -1, 1]
let dy = [1, -1, 0, 0]
var cLocation = [Int]()
for i in 0..<h{
arr.append(readLine()!.map{$0})
for j in 0..<w{
if arr[i][j] == "C"{
cLocation.append(i)
cLocation.append(j)
}
}
}
arr[cLocation[0]][cLocation[1]] = "."
//print(cLocation)
func bfs(){
var visited = Array(repeating: Array(repeating: Int.max, count: 10001), count: 10001)
var queue = [( (Int, Int), Int, Int )]() //x, y, 현재 큐의 진행방향, 거울개수
for i in 0..<4{
queue.append(((cLocation[0], cLocation[1]),i ,0))
}
visited[cLocation[0]][cLocation[1]] = 0
var idx = 0
while queue.count > idx {
let pop = queue[idx]
let x = pop.0.0
let y = pop.0.1
let direct = pop.1
let mirrorCnt = pop.2
idx += 1
for i in 0..<4{ //미래 진행방향
let nx = x + dx[i]
let ny = y + dy[i]
var nCnt = mirrorCnt
if nx < 0 || nx >= h || ny < 0 || ny >= w || arr[nx][ny] == "*"{continue}
if direct != i{
nCnt += 1
}
if visited[nx][ny] >= nCnt {
visited[nx][ny] = nCnt
queue.append(((nx, ny), i, nCnt))
}
}
}
print(visited[cLocation[2]][cLocation[3]])
}
bfs()
댓글