여담
사실 작년 여름 인턴 시험보면서 풀어봤던 문제이다.
그때는 못풀었다.
시간이 부족했는데, 즉 내 실력이 부족했기 때문이다.
그래서 이번주 카카오 인턴 시험을 한번 더 치는김에 풀어보기로 했는데 당시 풀지 못했던 이 문제를 풀고자 했다.
문제에 대해
가장 본질적인 문제의 요지는 효율성을 챙기는 완전 탐색 이다.
알고리즘적 요소는 BFS가 첨가되고 쓸데없는 연산과정을 빼면 된다.
아마, 이 문제의 노드 20만개 갯수를 보고 "BFS??! 말도 안되는 소리!!" 라고 할수도 있는데,
나도 처음부터 이게 될거라는 확신은 없었다.
그냥 중간에 불순 요소 빼고 최적화 하다보니 "어? 이거 될것같은데?" 라는 생각이 들었을뿐이다.
잡설이 조금 길었다.
개발자 답게 코드로 얘기할 시간이 왔다.
var graph : [[Int]] = [[Int]](repeating: q, count: n)
for x in path {
graph[x[0]].append(x[1])
graph[x[1]].append(x[0])
}우선 위와 같이 맵을 만들어줄 필요가 있다.
행렬로 그냥 주면 좀 좋겠냐만은 아무래도 Node의 개수가 20만개이니 만큼 20만 x 20만의 행렬을 주진 못할 것이고, 또 문제의 조건에 나와있듯 Nested 되어있는 그래프가 아니니 만큼 간결한 인접 리스트로 만드는것이 좋은 선택일 것이다.
var visit : [Int] = []
var locked : [Int] = [Int](repeating: -1, count: n)
var lock : [Int] = [Int](repeating: -1, count: n)
for i in 0...n {
visit.append(i)
}
for x in order {
locked[x[1]] = x[0]// 누구에 의해 잠겼는지
lock[x[0]] = x[1] // 누구를 잠갔는지
}그 다음에는, 방문 여부에 대한 visit배열, 누군가에 의해 잠겨 있는 locked와 누군가를 잠가버린 lock 배열을 선언하고 초기화 했다.
대채적으로 visit은 자기 자신의 index를 갖길 바랬고, 만약 탐방했다면 음수로 조절하여 바꿀수 있게끔 조정하였다.
lock, locked도 누군가에 의해 잠겨있는지에 대한 확인은 양수이므로, 만약 잠겨있지 않거나 잠그지 않았다면 -1을 가지게 했다.
if locked[0] != -1 {
return false
}위가 굉장히 중요한 코드인데.. 만약 시작점인 0이 잠겨있다면 앞으로 전진을 할수가 없다.
꼭 조건체킹을 해주도록 하자.
이제부터 입사할려고 코딩테스트를 준비했다면 한번쯤은 해봤을만한 BFS를 적용해 보도록 하자.
q.append(0)
if locking[0] != -1{
locked[locking[0]] = -1
locking[0] = -1
}
visit[0] = -2시작이 중요하다. 0에서 시작하니 0을 넣어주는것은 맞지만, 0에의해 잠겨있는 Node가 존재할수도 있다.
역시 여기서도 먼저 조건을 체킹해주고 가자.
이렇게 조건을 다 체킹해줬다면 나머지는 간단한 BFS일뿐이다.
while q.count > 0 {
let now = q[0]
q.removeFirst()
for next in graph[now] {
if visit[next] == -2 {// 1
continue
}
else{
if locked[next] != -1 { // 2
visit[next] = -1
}else{// 3
if locking[next] != -1 { // 4
let belocked = locking[next]
locking[next] = -1
locked[belocked] = -1
if visit[belocked] == -1 {
visit[belocked] = -2
q.append(belocked)
}
}
visit[next] = -2
q.append(next)
}
}
}
}간단하게 위와 같이 BFS코드를 짤수 있다.
우선 하나하나씩 보기 전에, Swift로 코드를 짯을때 Queue에서 그닥 좋지 않은점이 한가지가 있는데
queue에 관한것이다. enque는 O(1)이지만 removeFirst() 메소드로 deque했을 경우 O(N)이 걸리게 된다.
사실 queue에서 빼고 넣는 문제가 이 문제의 당낙을 좌우하진 않지만 그래도 조금 이라도 더 빠른 속도를 원한다면 queue의 구조 개선을 신경쓰면 좋을 것 같다.
그리고, 이제 BFS코드를 하나씩 보자
if visit[next] == -2 {// 1
continue
}그냥 방문했던곳은 다시 방문하지 않게끔 해주는 코드다.
방문했던 곳의 처리를 봤다면 이제 방문하지 않은 곳에 대한 코드를 봐야할 것인데 다음과 같다.
if locked[next] != -1 { // 2
visit[next] = -1
}else{// 3
if locking[next] != -1 { // 4
let belocked = locking[next]
locking[next] = -1
locked[belocked] = -1
if visit[belocked] == -1 {
visit[belocked] = -2
q.append(belocked)
}
}
visit[next] = -2
q.append(next)
}
}첫 번째로 누군가에 의해 잠겨있는지 확인을 한다.
만약 누군가에 의해 잠겨 있다면, 가지는 못하지만 "어떻게든 다시 돌아올수 있기 때문에" visit배열에 -1을 저장해놓고 탐색을 멈춘다.
그리고 두번 째로 누군가에 의해 잠겨있지 않다면, 이 Node가 누군가를 잠가놓진 않았는지 확인을 한다.
만약 누군가를 잠가놓았다면, 방문시 모든 잠금을 해제할수있다.
지금 Node가 잠갔다는 상태를 해제하고, 또 잠겨있는 Node의 상태 역시 해제한다.
또한 만약 이전에 내가 잠겨있는 Node를 방문한적이 있다면 해당 노드에서 다시 탐색할수 있도록 Queue에 넣어준다.
마지막으로 현재 노드는 잠겨있지 않아 어떻게든 탐색이 가능하기 때문에 Queue에 넣고 탐색을 진행한다.
전체코드는 다음과 같다.
코드 리뷰
- 모듈화를 신경쓰고싶다.
- 의미있는 변수 네이밍을 사용하고 싶다.
- 동작에 대한 명확한 규명을 잘 하자.
