Programmers) Lv3 [2020카카오공채] 기둥과 보 설치

출처: https://programmers.co.kr/learn/courses/30/lessons/60061

분류: Lv3 

---

접근방식

문제에 제시된 조건대로 잘 구현할 수 있는지 구현 능력을 파악하는 문제입니다.
특별한 기술이나 이론이 필요한 문제는 아닙니다.
조건에 맞게 잘 구현하면 됩니다... 잘 잘.. 잘....

네... 정답률 1.9% ... 👀

---

문제의 핵심은 기둥과 보를 설치하고 삭제할 때 조건을 명확하게 이해하고 구현할 수 있느냐에 있습니다.
생각보다 여러가지 상황이 있기 때문에 각 케이스 별로 잘 분류해서 명확하게 풀어야겠어요.

저는

• 설치 / 삭제
  • 기둥 / 보
    • 상황별

이런식으로 쪼개서 케이스를 최대한 나눠서 풀어보았습니다.

 

해결방법

먼저 설치부터 확인해보죠.
설치는 기둥 설치, 보 설치 상황이 있겠죠 ?
각 상황에서 문제가 되는 제한 사항들을 잘 파악하고 이해했다면
케이스가 좀 많아서 그렇지 문제 자체는 어렵지 않습니다.

참고로 저는 map 이라는 3차원 배열을 정의해서 

x, y, a ( 0 == 기둥, 1 == 보) 
map[x][y][a] 가 세워졌으면 1
아니면 0 으로 정의했습니다.

그리고 문제에서 각 케이스가 map 의 범위를 벗어나지 않는지 범위 체크도 잘 해줘야겠죠 :)

 

[ 기둥 설치 ]

기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.

문제에서 기둥은 위와과 같이 가정합니다. 

즉, (x,y) 에 기둥을 세운다고 할 때, 다음과 같이 3가지 경우에만 기둥을 세울 수 있겠네요.

• 기둥은 바닥위에 있거나 ( y == 0 )
• 보의 한쪽 끝에 있거나
• 다른 기둥 위에 있거나 
  

// 설치
if a == 0 {
  // 기둥 추가
  guard
    y == 0 ||
    map[x][y][1] == 1 ||
    (x-1 >= 0 && map[x-1][y][1] == 1) ||
    (y-1 >= 0 && map[x][y-1][0] == 1)
    else {
    	return
  }

  //print("추가")
  map[x][y][a] = 1
}

 

 

[보 설치]

보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

(x, y) 에 보를 설치한다고 할 때는 다음과 같습니다.

• 한쪽 끝 부분이 기둥 위에 있거나
• 양쪽 끝 부분이 다른 보와 동시에 연결되어 있거나

 

else {
  // 보 추가
  guard
    map[x][y-1][0] == 1 ||
    (x+1 <= map.count && y-1 >= 0 && map[x+1][y-1][0] == 1) ||
    (x-1 >= 0 && x+1 <= map.count && map[x-1][y][1] == 1 && map[x+1][y][1] == 1)
    else {
    	return
  }

  //print("추가")
  map[x][y][a] = 1
}

 

 

[ 기둥 삭제 ]

기둥이나 보는 다른 기둥이나 보 혹은 벽면에 위에 쌓이는 것이기 때문에

삭제되었을 때는 삭제된 기둥이나 보 위에 쌓아진 녀석들이 문제가 되겠죠?

따라서 끝 부분에 신경써야 합니다.

삭제될 기둥 끝에 기둥이나 보가 있다면, 다음과 같은 경우에만 삭제가 가능합니다.

 

// 삭제
if b == 0 {
  if a == 0 {
  // 기둥 삭제

  // 삭제 될 기둥 끝에 기둥이 있을 때,
  if y+1 <= map.count, map[x][y+1][0] == 1 {
  	guard (x-1 >= 0 && map[x-1][y+1][1] == 1) || map[x][y+1][1] == 1 else { return }
  }

  // 삭제 될 기둥 끝에 보가 있을 때,
  if y+1 <= map.count, map[x][y+1][1] == 1 {
    guard
      (x+1 <= map.count && map[x+1][y][0] == 1) ||
      ((x-1 >= 0 && map[x-1][y+1][1] == 1) && (x+1 <= map.count && map[x+1][y+1][1] == 1))
      else {
      	return
    }
  }

  if y+1 <= map.count, x-1 >= 0, map[x-1][y+1][1] == 1 {
    guard
      (x-1 >= 0 && map[x-1][y][0] == 1) ||
      ((x-2 >= 0 && map[x-2][y+1][1] == 1) && map[x][y+1][1] == 1)
      else {
        return
    }
  }
  
  // 문제가 없다면 삭제
  map[x][y][a] = 0
}

 

 

[ 보 삭제 ]

보도 마찬가지로 보 끝에 기둥이나 보가 있을 경우

언제 문제가 되는지 확인하면 됩니다.

// 보 삭제
else {

  // 보 끝에 기둥이 있을 때
  if x+1 <= map.count, map[x+1][y][0] == 1 {
  	guard (y-1 >= 0 && map[x+1][y-1][0] == 1) || map[x+1][y][1] == 1 else { return }
  }

  if map[x][y][0] == 1 {
    guard
      (y-1 >= 0 && map[x][y-1][0] == 1) ||
      (x-1 >= 0 && map[x-1][y][1] == 1)
      else {
      	return
    }
  }

  // 보 끝에 보가 있을 때
  if x+1 <= map.count, map[x+1][y][1] == 1 {
    guard
      (x+1 <= map.count && y-1 >= 0 && map[x+1][y-1][0] == 1) ||
      (x+2 <= map.count && y-1 >= 0 && map[x+2][y-1][0] == 1)
      else {
      	return
    }
  }

  if x-1>=0, map[x-1][y][1] == 1 {
    guard
      (y-1 >= 0 && map[x-1][y-1][0] == 1) ||
      (y-1 >= 0 && map[x][y-1][0] == 1)
      else {
      	return
    }
  }

  // 삭제
  map[x][y][a] = 0
}

 

 

---

하 머나먼 여정을 오느라 수고하셨습니다.

케이스를 잘 나누지 못하면 너무 복잡하죠... ㅠㅠ 

푸는 것도 푸는거지만 제한된 시간이 있기 때문에 빠르고 정확하게 푸는게 정말 중요한 것 같아요.

언젠쯤 그럴 수 있을까요 😰

 

조금이라도 도움이 되셨으면 좋겠습니다. 

감사합니다 :)

 

 

혹시 전체 코드가 궁금하시다면

import Foundation

// map[x][y][a] == 0 or 1
var map = [[[Int]]]()

func pilar(to frame: [Int]) {
    
    let x = frame[0]
    let y = frame[1]
    let a = frame[2]
    let b = frame[3]
    //print(x, y, a, b)
    
    if b == 0 {
        // 삭제
        if a == 0 {
            // 기둥 삭제
            
            // 삭제 될 기둥 끝에 기둥이 있을 때,
            if y+1 <= map.count, map[x][y+1][0] == 1 {
                guard (x-1 >= 0 && map[x-1][y+1][1] == 1) || map[x][y+1][1] == 1 else { return }
            }
            
            // 삭제 될 기둥 끝에 보가 있을 때,
            if y+1 <= map.count, map[x][y+1][1] == 1 {
                guard
                    (x+1 <= map.count && map[x+1][y][0] == 1) ||
                    ((x-1 >= 0 && map[x-1][y+1][1] == 1) && (x+1 <= map.count && map[x+1][y+1][1] == 1))
                else {
                    return
                }
            }
            
            if y+1 <= map.count, x-1 >= 0, map[x-1][y+1][1] == 1 {
                guard
                    (x-1 >= 0 && map[x-1][y][0] == 1) ||
                    ((x-2 >= 0 && map[x-2][y+1][1] == 1) && map[x][y+1][1] == 1)
                else {
                    return
                }
            }
            
            //print("삭제")
            map[x][y][a] = 0
            
        } else {
            // 보 삭제
            
            // 보 끝에 기둥이 있을 때
            if x+1 <= map.count, map[x+1][y][0] == 1 {
                guard (y-1 >= 0 && map[x+1][y-1][0] == 1) || map[x+1][y][1] == 1 else { return }
            }
            
            if map[x][y][0] == 1 {
                guard
                    (y-1 >= 0 && map[x][y-1][0] == 1) ||
                    (x-1 >= 0 && map[x-1][y][1] == 1)
                else {
                    return
                }
            }
            
            // 보 끝에 보가 있을 때
            if x+1 <= map.count, map[x+1][y][1] == 1 {
                guard
                    (x+1 <= map.count && y-1 >= 0 && map[x+1][y-1][0] == 1) ||
                    (x+2 <= map.count && y-1 >= 0 && map[x+2][y-1][0] == 1)
                else {
                    return
                }
            }
            
            if x-1>=0, map[x-1][y][1] == 1 {
                guard
                    (y-1 >= 0 && map[x-1][y-1][0] == 1) ||
                    (y-1 >= 0 && map[x][y-1][0] == 1)
                else {
                    return
                }
            }

            //print("삭제")
            map[x][y][a] = 0
        }
        
    } else {
        // 추가
        if a == 0 {
            // 기둥 추가
            guard
                y == 0 ||
                map[x][y][1] == 1 ||
                (x-1 >= 0 && map[x-1][y][1] == 1) ||
                (y-1 >= 0 && map[x][y-1][0] == 1)
            else {
                return
            }
            
            //print("추가")
            map[x][y][a] = 1
        } else {
            // 보 추가
            
            guard
                map[x][y-1][0] == 1 ||
                (x+1 <= map.count && y-1 >= 0 && map[x+1][y-1][0] == 1) ||
                (x-1 >= 0 && x+1 <= map.count && map[x-1][y][1] == 1 && map[x+1][y][1] == 1)
            else {
                return
            }
            
            //print("추가")
            map[x][y][a] = 1
        }
    }
}

func solution(_ n:Int, _ build_frame:[[Int]]) -> [[Int]] {
        
    map = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: 2), count: n+1), count: n+1)
    
    for frame in build_frame {
        pilar(to: frame)
        
    }
    
    var result = [[Int]]()
    
    
    for (i, m1) in map.enumerated() {
        for (j, m2) in m1.enumerated() {
            for (z, a) in m2.enumerated() {
                if a == 1 {
                    result.append([i, j, z])
                }
            }
        }
    }
    
    return result
}