Jenikeju

문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

내가 푼 풀이

접근방법: 다익스트라

처음에 그래프를 저장할 때 인접행렬로 저장했다가, 30만 x 30만이라서  메모리 초과가 일어났다.

인접리스트로 그래프를 저장하고 다익스트라 알고리즘을 이용한다.

다익스트라는 선형탐색으로 하였지만 겨우 시간초과에 안맞게 통과된거같다.

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1], K = input[2], X = input[3]
var md = Array(repeating: 1000000, count: N+1)
var graph = [Int: [Int]]()

// 인접리스트
for i in 0..<M {
    let road = readLine()!.split(separator: " ").map{Int(String($0))!}
    if graph[road[0]] == nil {
        graph[road[0]] = [road[1]]
    } else {
        graph[road[0]]!.append(road[1])
    }
}

var queue = [(cur: X, cost: 0)]
md[X] = 0
// 다익스트라
while !queue.isEmpty {
    let node = queue.removeLast()
    var next = graph[node.cur]
    // 그다음 인접노드가 없거나 이미 K보다 크다면 의미가 없으므로 건너뜀
    if next == nil || node.cost > K { continue }
    // 인접한 노드들의 최단거리정보를 저장하고, 다음 노드 탐색
    for i in next! {
        if md[i] > md[node.cur] + 1 {
            md[i] = md[node.cur] + 1
            queue.append((cur: i, cost:md[i]))
        }
    }
    
}

// 출력
var find = false
for i in 0..<md.count {
    if md[i] == K {
        find = true
        print(i)
    }
}

if !find {
    print(-1)
}

1. 주어진 버스들로 2차원 배열을 만든다 (arr[i][j]: i도시에서 j도시까지의 거리)

1-1. 출발지와 도착지가 동일한경우 더 작은값을 넣는다.

2. 최단거리를 저장할 배열을 만든다.

3. 다익스트라 탐색을 이용해 이동가능한 버스를 통해 최단거리를 갱신한다.

4. 최종 갱신된 최단거리 배열에서 도착점의 원소 출력

import Foundation

// 입력받기
let N = Int(readLine()!)!
let M = Int(readLine()!)!
var cities = Array(repeating: Array(repeating: Int.max, count: N+1), count: N+1)
var bus = [[Int]]()
for i in 0..<M {
    let b = readLine()!.split(separator: " ").map{Int(String($0))!}
    bus.append(b)
}
let direct = readLine()!.split(separator: " ").map{Int(String($0))!}

// 2차원 배열로 만들기 cities[i][j] : i도시에서 j도시로 가는 거리
// 출발지와 목적지가 동일한 버스가 주어진다면 값비교해서 최솟값만 넣기
for i in bus {
    if cities[i[0]][i[1]] == Int.max {
        cities[i[0]][i[1]] = i[2]
    } else {
        if cities[i[0]][i[1]] > i[2] {
            cities[i[0]][i[1]] = i[2]
        }
    }
    
}
// 최단경로를 저장해놓을 배열
var md = Array(repeating: Int.max, count: N+1)
md[direct[0]] = 0
var queue = [(cur: direct[0], cost: 0)]

// 탐색
while !queue.isEmpty {
    let node = queue.removeFirst()
    for i in 1...N {
        // 현재 도시와 인접도시가 버스를 통해 갈 수 있고, 저장된 최단거리보다 더 짧다면 갱신해주고, 큐에 삽입
        if cities[node.cur][i] != Int.max && md[node.cur] + cities[node.cur][i] < md[i] {
            md[i] = md[node.cur] + cities[node.cur][i]
            queue.append((cur: i, cost: md[i]))
        }
    }
}
print(md[direct[1]])

알고리즘 문제를 풀면서, 최단경로를 구하는 문제에서 BFS 혹은 DFS를 이용해 문제를 푸려다, 늘 시간초과와 함께했다..

이번에는 특정 노드로 가는데 걸리는 최단경로를 구하기에 용이한 다익스트라 알고리즘을 배우려한다.

다익스트라 알고리즘

 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 최단경로를 구하는 탐색 알고리즘이다.

이는 실생활에서 최단경로를 구하는데 용이한 알고리즘으로 어떠한 그래프든 방향과 상관이 없지만, 실생활에서 음수의 경로는 없듯이

가중치가 음수인 그래프는 사용할 수 없다.

다익스트라 알고리즘은 하나의 최단거리를 구할때, 이전의 최단거리를 이용하여 구한다는점이 다이나믹 프로그래밍의 특징이라 알 수 있다.

다익스트라는 하나의 노드로 부터 최단경로를 구하는 알고리즘 이지만, 플로이드-워셜 알고리즘은 모든 노드쌍들의 최단거리를 구한다.

다익스트라의 확장된 알고리즘으론 A* 알고리즘이 있다.

알고리즘 작동 과정

이 그래프에서 우리는 A지점에서 출발 한다고 하자.

A에서 출발해 인접한 노드들로 갈 것이다. (B, C)

현재 우리는 B,C의 최단거리를 알고 있다.(B = 5, C = 1)

그 다음 A에서 C로 간다면, C의 인접한 노드들의 최단거리를 갱신하게되며, A에서B로가는 최단거리는 A - C - B = 3 이 된다.

-> A에 있을땐 B와의 최단거리는 5로 알고있지만, C로 가보았다면 B의 최단거리는 3이 됨을 알 수 있다.

이렇게 인접한 노드들의 거리를 이용해, 현재 최단거리의정보를 계속 갱신해나가는 것이다.

1. 출발점을 지정한다.

2. 출발노드와 인접한 노드들의 최단거리를 갱신한다.

3. 인접한 노드들 중 거리가 짧은 노드를 선택한다.

4. 선택한노드와 인접한 노드의 거리로 최단거리 정보를 갱신한다.

5. 3-4 반복

A지점에서는 B와 C로 갈 수 있고, D, E는 갈 수 없다.

이를 표로 나타내면 다음 과 같다. 이 표는 현재 최단거리의 정보를 저장한 표다.

그 다음노드는 인접한 노드들중 가장 가까운 거리를 먼저 간다.

C에 도착했다면 현재 저장된 최단거리와 C와 인접한 노드들의 거리를 계산하여 갱신한다.

B: C까지의 최단거리 + (C-B) = 3

D: C까지의 최단거리 + (C-D) = 5 

그 다음 방문하지 않은 노드중 가장 비용이 적은 노드를 고른다.

B를 방문했을때, 인접한노드들과 최단거리정보와 비교한다.

D: B까지의 최단거리 + (B-D): 4

E: B까지의 최단거리 + (B-E): 7

그다음 방문하지 않은 노드중 비용이 적은 노드를 방문한다.

D를 방문했을때, 인접한노드 E의 최단거리를 갱신한다.

E: D까지의 최단거리 + E = 4 + 2 = 6

마지막 남은 노드를 방문한다.

해당 노드를 방문해도 최단거리 배열은 같다.

다익스트라 알고리즘은 가중치가 가장 낮은 인접 노드를 우선으로 탐색하지만,

선형탐색으로 가중치와 관계없이 인접한 노드를 탐색하는 방법 도 있다.

하지만 선형탐색으로 탐색한다면 O(N^2)가 걸리고, Heap구조를 이용해 구현한다면 O(NlogN)만큼 걸리게된다.

선형탐색은 노드 수가 많을수록 치명적이다.

선형탐색 O(N^2)

import Foundation

// 그래프 2차원배열 graph[1][2] -> 노드1과 노드2의 가중치, 10000000은 임의의 큰 값 (연결되지않음)
var graph = [
    [0, 5, 1, 10000000, 10000000],
    [5, 0, 2, 1, 4],
    [1, 2, 0, 4, 10000000],
    [10000000, 1, 4, 0, 2],
    [10000000, 4, 10000000, 2, 0]
]
// 출발점 지정
var needVisit = [(cur: 0, cost: 0)]

// 현재 최단거리를 저장할 배열
// ex) minDistances[1]: 출발점에서 노드1까지의 최단거리
var minDistances = Array(repeating: 10000000, count: graph.count)
minDistances[0] = 0

// 탐색
while !needVisit.isEmpty {
    let node = needVisit.removeFirst()
    // 노드와 인접한 노드들을 탐색한다.
    for i in 0..<graph[node.cur].count {
        let dist = graph[node.cur][i]
        // 노드와 연결되어 있고, 현재 저장된 최단거리 + 해당노드와의 거리가 더 작은값이라면 갱신
        // 갱신된 노드와 최단거리와 함께 큐에 재삽입
        if dist != 10000000 && node.cost + dist < minDistances[i] {
            minDistances[i] = node.cost + dist
            needVisit.append((cur: i, cost: minDistances[i]))
        }
    }
}

결과:

// 결과
// A와의 인접노드: B,C
selectedNode: (cur: 0, cost: 0)
before: [0, 10000000, 10000000, 10000000, 10000000]
after: [0, 5, 1, 10000000, 10000000]
needVisit: [(cur: 1, cost: 5), (cur: 2, cost: 1)]

// B와의 인접노드: A,C,D,E
selectedNode: (cur: 1, cost: 5)
before: [0, 5, 1, 10000000, 10000000]
after: [0, 5, 1, 6, 9]
needVisit: [(cur: 2, cost: 1), (cur: 3, cost: 6), (cur: 4, cost: 9)]

// C와의 인접노드: A,B,D
// 여기서 B의 최단거리가 C를 통해 가는게 더 작은값임을 알고, 갱신하고 B를 재탐색하기위해 큐에 삽입)
// D도 갱신되어 큐에 삽입
selectedNode: (cur: 2, cost: 1)
before: [0, 5, 1, 6, 9]
after: [0, 3, 1, 5, 9]
needVisit: [(cur: 3, cost: 6), (cur: 4, cost: 9), (cur: 1, cost: 3), (cur: 3, cost: 5)]

// D와의 인접노드: B,C,E
// E의최단거리 갱신되어, E를 큐에 삽입
selectedNode: (cur: 3, cost: 6)
before: [0, 3, 1, 5, 9]
after: [0, 3, 1, 5, 8]
needVisit: [(cur: 4, cost: 9), (cur: 1, cost: 3), (cur: 3, cost: 5), (cur: 4, cost: 8)]

// E와의 인접노드: B,D
// 갱신되지않음.
selectedNode: (cur: 4, cost: 9)
before: [0, 3, 1, 5, 8]
after: [0, 3, 1, 5, 8]
needVisit: [(cur: 1, cost: 3), (cur: 3, cost: 5), (cur: 4, cost: 8)]

// 아래부턴 갱신된 최단거리를 통해 다시 노드를 선택하여 인접한 노드와의 최단거리를 갱신한다.
selectedNode: (cur: 1, cost: 3)
before: [0, 3, 1, 5, 8]
after: [0, 3, 1, 4, 7]
needVisit: [(cur: 3, cost: 5), (cur: 4, cost: 8), (cur: 3, cost: 4), (cur: 4, cost: 7)]

selectedNode: (cur: 3, cost: 5)
before: [0, 3, 1, 4, 7]
after: [0, 3, 1, 4, 7]
needVisit: [(cur: 4, cost: 8), (cur: 3, cost: 4), (cur: 4, cost: 7)]

selectedNode: (cur: 4, cost: 8)
before: [0, 3, 1, 4, 7]
after: [0, 3, 1, 4, 7]
needVisit: [(cur: 3, cost: 4), (cur: 4, cost: 7)]
// E 갱신, 갱신된 최단거리와 함께 큐에 재삽입
selectedNode: (cur: 3, cost: 4)
before: [0, 3, 1, 4, 7]
after: [0, 3, 1, 4, 6]
needVisit: [(cur: 4, cost: 7), (cur: 4, cost: 6)]

selectedNode: (cur: 4, cost: 7)
before: [0, 3, 1, 4, 6]
after: [0, 3, 1, 4, 6]
needVisit: [(cur: 4, cost: 6)]

selectedNode: (cur: 4, cost: 6)
before: [0, 3, 1, 4, 6]
after: [0, 3, 1, 4, 6]
needVisit: []

Reference:

https://m.blog.naver.com/ndb796/221234424646

내가 푼 풀이

접근방법: 브루탈포스와 기하학

- 문제에서 힌트를 얻었는데, 두 지붕을 잇는 선분이 있는데, 다른 빌딩이 그 선분을 접하거나 넘으면 안된다고 한다.

- 이는 두 지붕의 x,y좌표를 이용해 두 선을 잇는 직선의 방정식을 구하고, 그 사이의 빌딩들이 그 직선을 접하거나 넘으면 볼 수 없다고 판단한다.

- 직선의 방정식을 구해서 한 빌딩의 지붕 x,y좌표를 대입한다면, 주어진 방적식 y = ax + b 에 대입할 것이다.

- 여기서 대입하여 양쪽의 값을 비교하여 해당 빌딩이 직선을 넘는지, 접점인지 판단한다.

- y >= ax + b 의 경우, 해당 점은 직선과 접한 점이거나, 직선보다 위에 존재하는 점이다. (빌딩을 볼 수 없음)

- y < ax + b의 경우, 해당 점은 직선보다 아래 위치한 점이다. (빌딩을 볼 수 있음)

이 조건을 이용해 모든 경우의수를 따져보고 최댓값을 출력한다.

주의할점) a와 b를 구하고, 값을 비교하는 과정에서 소숫점이 날아가지 않게 적절한 형변환을 해주어야한다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
let buildings = readLine()!.split(separator: " ").map{Int(String($0))!}
var converted = [(x: Int, y: Int)]()
var result = Int.min
// 주어진 빌딩을 지붕의 좌표로 변환
for i in 0..<buildings.count {
    converted.append((x: i+1,y: buildings[i]))
}

// 모든 경우 탐색
for i in 0..<converted.count {
    var count = 0
    for j in 0..<converted.count {
        // 같은 빌딩이면 패스
        if i == j { continue }
        var see = true
        let x1: Double = Double(converted[i].x)
        let x2: Double = Double(converted[j].x)
        let y1: Double = Double(converted[i].y)
        let y2: Double = Double(converted[j].y)
        
        // y = ax + b 의 방정식중 a,b를 구하는 과정
        let a = (y2 - y1) / (x2 - x1)
        let b = y1 - (x1 * a)
        
        // 현재 빌딩 이전에 위치한 빌딩들과의 탐색
        if i > j {
            for k in j+1..<i {
                let leftValue: Double = Double(converted[k].y)
                let rightValue: Double = Double(converted[k].x) * a + b
                if leftValue >= rightValue {
                    see = false
                    break
                }
            }
        } else {
            // 현재 빌딩 이후에 위치한 빌딩들과의 탐색
            for k in i+1..<j {
                let leftValue: Double = Double(converted[k].y)
                let rightValue: Double = Double(converted[k].x) * a + b
                if leftValue >= rightValue {
                    see = false
                    break
                }
            }
        }
        if see {
            count += 1
        } else {
        }
    }
    result = max(result, count)
}
print(result)

내가 푼 풀이

접근방법 1. DFS 백트래킹 (시간초과)

최단시간을 구하는 문제는 BFS와 맞다..

1. 미로를 진입해 레버를 찾기까지 걸린시간을 구한다.

2. 레버를 찾았다면 레버위치에서 출구까지의 걸린시간을 더한다.

3. 레버를 못찾거나, 탈출구를 못찾았다면 -1출력

-> 이방법을 처음에 생각해서 사용해봤는데, 시간초과를 피할 수 없었다.

최악의 경우 모든 길을 찾아야하므로 BFS를 이용하기로 했다.

접근방법 2. BFS

DFS를 실패하고 바로 BFS를 설계했지만, BFS도 시간초과가 좀 났었다.

BFS는 인접한 지점 먼저 탐색이지만, 이미 탐색한곳은 재탐색을 하지 않게 해줘야한다.

재탐색여부를 저장하는 visited[Bool]에 값을 넣는 시점에따라 완전탐색, 조건에맞는 부분탐색을 하게 되었다.

BFS는 탐색시작지점에서 인접한 노드를 저장한다.

저장한 노드를 선입선출(큐와 같이)방식으로 빼내서 탐색을 실시한다.

여기서 탐색된곳임을 지정하는 과정이 다음노드를 넣을때 설정해줘야한다.

예로 [노드: 인접한노드]로 주어졌을때, [1: 2345] [2: 3456] [3: 45678] 이라면

1번 노드를 탐색했을때, 다음탐색은 2 - 3 - 4 - 5 를 탐색한다.

2번 노드를 탐색했을때, 다음탐색은 3 - 4 - 5 - 3 - 4 - 5 - 6 이된다.

2번과 인접한 노드는 이미 다음순서로 지정되있어서 중복탐색하게된다.

이렇게 큐에 쌓이지 않도록 하려면 인접한 노드를 넣을때, 그 노드는 이미 탐색이 되었다 라고 지정해줘야한다.

그러면 조건속에서 2번 노드를 탐색할때, 2번의 인접노드들은 이미 탐색된 노드들로 판단되므로, 큐에 쌓이지않는다.

이 점을 새기며, 코드를 수정하니 시간초과가 뜨지 않았다.

import Foundation

func solution(_ maps:[String]) -> Int {
    // 입력
    var map = [[String]]()
    var visited = [[Bool]]()
    var counted = [[Int]]()
    var start = (x: 0, y: 0)
    var lever = (x: 0, y: 0)
    var end = (x: 0, y: 0)
    for i in 0..<maps.count {
        let s = maps[i].map{String($0)}
        visited.append(Array(repeating: false, count: s.count))
        counted.append(Array(repeating: 10000000, count: s.count))
        map.append(s)
        for j in 0..<s.count {
            if map[i][j] == "S" {
                start = (x: j, y: i)
            }
            if map[i][j] == "L" {
                lever = (x: j, y: i)
            }
            if map[i][j] == "E" {
                end = (x: j, y: i)
            }
        }
    }
    // BFS
    var needVisit = [(x: start.x, y: start.y)]
    var index = 0
    var dx = [0,1,0,-1]
    var dy = [1,0,-1,0]
    var copyVisited = visited
    var copyCounted = counted
    copyCounted[start.y][start.x] = 0
    // lever위치까지의 BFS
    while index < needVisit.count {
        let cur = needVisit[index]
        
        index += 1
        if cur.x == lever.x && cur.y == lever.y { break }
        for i in 0..<4 {
            let mx = cur.x + dx[i]
            let my = cur.y + dy[i]
            
            if mx < 0 || mx >= map[0].count || my < 0 || my >= map.count {
                continue
            }
            if copyVisited[my][mx] || map[my][mx] == "X" { continue }
            copyVisited[my][mx] = true // 다음 노드를 큐에 넣을때, 이미 탐색된곳이라 지정 (중복탐색방지)
            copyCounted[my][mx] = min(copyCounted[my][mx], copyCounted[cur.y][cur.x] + 1)
            needVisit.append((x: mx, y: my))
        }
    }
    // 레버에 도착하지 못했다면 1000000(임의의 큰수)
    let arriveLeverTime = copyCounted[lever.y][lever.x]
    if arriveLeverTime >= 10000000 { return -1 }
    
    needVisit = [(x: lever.x, y: lever.y)]
    index = 0
    copyCounted = counted
    copyCounted[lever.y][lever.x] = 0
    copyVisited = visited
    // end위치까지의 BFS
    while index < needVisit.count {
        let cur = needVisit[index]
        

        index += 1
        if cur.x == end.x && cur.y == end.y { break }
        for i in 0..<4 {
            let mx = cur.x + dx[i]
            let my = cur.y + dy[i]
            
            if mx < 0 || mx >= map[0].count || my < 0 || my >= map.count {
                continue
            }
            if copyVisited[my][mx] || map[my][mx] == "X" { continue }
            
            copyCounted[my][mx] = min(copyCounted[my][mx], copyCounted[cur.y][cur.x] + 1)
            copyVisited[my][mx] = true // 다음 노드를 큐에 넣을때, 이미 탐색된곳이라 지정 (중복탐색방지)
            needVisit.append((x: mx, y: my))
        }
    }
    // 출구에 도착하지 못했다면 1000000(임의의 큰수)
    let arriveEndTime = copyCounted[end.y][end.x]
    if arriveEndTime >= 10000000 { return -1 }

    return arriveLeverTime + arriveEndTime
}

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

• x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• rows는 2 이상 100 이하인 자연수입니다.
• columns는 2 이상 100 이하인 자연수입니다.
• 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
  • 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
• queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
• queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
  • x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
  • 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

---

 

입출력 예시

rows	columns	queries	result
6	6	[[2,2,5,4],[3,3,6,6],[5,1,6,3]]	[8, 10, 25]
3	3	[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]]	[1, 1, 5, 3]
100	97	[[1,1,100,97]]	[1]

내가 푼 풀이

- 회전을 구현하여 해당 범위를 교체하고, 최솟값을 저장한다.

- 따로 다른 알고리즘 없이 회전하는 동작을 구현하면 된다.

import Foundation

func solution(_ rows:Int, _ columns:Int, _ queries:[[Int]]) -> [Int] {
    var board = Array(repeating:Array(repeating: 0, count: columns+1), count: rows+1)
    var answer = [Int]()
    // 입력
    for i in 1...rows {
        for j in 1...columns {
            board[i][j] = ((i-1) * columns + j)
        }
    }
    
    // 쿼리 돌리기
    var b = board
    for query in queries {
        var a = moveNums(query, b)
        var minNum = a.removeLast()
        answer += minNum
        b = a
    }
    
    return answer
}

func moveNums(_ query: [Int],_ arr: [[Int]]) -> [[Int]] {
    var dx = [1, 0, -1, 0]
    var dy = [0, 1,  0, -1]
    var a = arr
    var mx = query[1]
    var my = query[0]
    var rc = query[3] - query[1]
    var cc = query[2] - query[0]
    var previous = a[my][mx]
    var minNum = a[my][mx]
    // 회전하며, 저장된 값과 그 다음의 값을 비교해 최솟값 갱신
    for i in 0..<4 {
        if i == 0 || i == 2 {
            for j in 0..<rc {
                mx += dx[i]
                my += dy[i]
                minNum = min(minNum, a[my][mx])
                var tmp = a[my][mx]
                a[my][mx] = previous
                previous = tmp
                
            }
        } else {
            for j in 0..<cc {
                mx += dx[i]
                my += dy[i]
                minNum = min(minNum, a[my][mx])
                var tmp = a[my][mx]
                a[my][mx] = previous
                previous = tmp
                
            }
        }
    }
    
    a.append([minNum])
    return a
}

나타난 오류 및 막힌점

RandomStudy 프로젝트 제작 중,

할 일을 추가하는 popUpView로 present 후, 데이터 추가한 뒤 dismiss로 돌아왔을때,

데이터를 전달하는 과정에서 어떻게 구성해야 할지 막히게 되었다.

첫번째 접근방법: viewWillAppear()

뷰가 나타날때 마다 실행되는 viewWillAppear 메서드를 이용해 갔다 온 뒤 데이터를 최신화하는 함수를 넣어두자.

그 전에 이 메서드가 작동하는지 확인하기 위해 메서드가 실행되면 viewWillAppear가 출력되도록 테스트 해봤다.

 // AddViewController.Swift
 override func viewWillAppear(_ animated: Bool) {
        print("viewWillAppear")
    }

 // AddPopUpViewController.Swift
 // 버튼을 누르면 dismiss하는 이벤트메서드
 @objc func addButtonTapped() {
        guard let text = self.textField.text else { return }
        if text == "" {
            errorLabel.text = "공백은 추가할 수 없습니다."
            errorLabel.isHidden = false
        } else {
            if viewModel.isContainsElement(str: text) {
                errorLabel.text = "같은 목록이 존재합니다."
                errorLabel.isHidden = false
            } else {
                errorLabel.isHidden = true
                viewModel.addData(str: text)
                self.dismiss(animated: true)
            }
        }
    }

<< 실행 결과 >>

버튼을 눌러서 dismiss를 실행해도 viewWillAppear가 프린트 되지 않았다.

이유를 찾아보니 이는 modalstyle과 연관이 있다고 한다.

fullscreen	automatic(기본값)	overscreen

보통 위와같이 modalstyle을 설정하는데, 설정하지 않으면 automatic으로 설정된다.

세가지를 비교해보았을때,

- fullscreen: 이전 뷰를 제거하고, 다음 뷰로 present한다.

- automatic, overscreen: 뷰가 present되고 이전 뷰는 뷰 계층구조에서 제거되지 않는다.

따라서 fullscreen만 viewWillAppear메서드가 작동되는이유는 다음 뷰로 이동하면서 이전뷰가 뷰 계층구조에서 제거되었기 때문에,

이전 뷰로 다시 돌아온다면 viewWillAppear메서드를 이용해 뷰가 나타날것을 알려줘야하기 때문이다.

뷰를 여기저기 이동하면서 다시 돌아올 때, 데이터를 최신화해야하는 과정이 필요하거나, 레이아웃을 변경해야한다면 viewWillAppear 자주 호출했었는데, modalstyle에 따라 사용을 유념해야겠다.

하지만 이 프로젝트에서 PopUpVC는 팝업된 작은 창을 나타내기위해선 fullscreen 방식과는 맞지 않았다.(배경이 검은색으로 아예 다른 창으로 이동하는 느낌이난다..)

두번째 접근방법으로 delegate패턴을 이용했다. https://jenikeju.tistory.com/267

나타난 오류 및 막힌점

RandomStudy 프로젝트 제작 중,

할 일을 추가하는 popUpView로 present 후, 데이터 추가한 뒤 dismiss로 돌아왔을때,

데이터를 전달하는 과정에서 어떻게 구성해야 할지 막히게 되었다.

델리게이트 패턴을 사용했지만 delegate = nil로 위임자를 못찾는 오류

두번째 접근방법: Delegate

두번째 방법은 delegate 방법이다.

PopUpVC에서 프로토콜을 선언해 데이터를 추가한다면, 프로토콜안 메서드를 데이터 받는 VC에서 메서드를 구현해 데이터를 최신화 해보려고 한다.

<AddVC>

// AddPopUpViewController.swift

protocol AddPopUpViewControllerDelegate: AnyObject {
    func sendedDataFromPopUp()
}

class AddPopUpViewController: UIViewController {
    weak var delegate: AddPopUpViewControllerDelegate?
    
    
     @objc func addButtonTapped() {
        guard let text = self.textField.text else { return }
        if text == "" {
            errorLabel.text = "공백은 추가할 수 없습니다."
            errorLabel.isHidden = false
        } else {
            if viewModel.isContainsElement(str: text) {
                errorLabel.text = "같은 목록이 존재합니다."
                errorLabel.isHidden = false
            } else {
                errorLabel.isHidden = true
                viewModel.addData(str: text)
                delegate?.sendedDataFromPopUp() // <--- 델리게이트 메서드
                self.dismiss(animated: true)
            }
        }
    }
   
}

-> 데이터를 보낼 곳에서 delegate을 선언해두고, 프로토콜을 만들고, 버튼을 누르면 위임자가 프로토콜의 메서드를 작동하도록 하였다.

<PopUpVC>

// AddViewController.swift
class AddViewController: UIViewController {
    
    private var popupVC = AddPopUpViewController()
    // 데이터 바인딩
    private func bindings() {
        popupVC.delegate = self
    }
    // PopUpVC로 가는 이벤트 메서드
     @objc func addCategory() {
        let addPopUpView = AddPopUpViewController()
        addPopUpView.modalPresentationStyle = .overFullScreen
        addPopUpView.modalTransitionStyle = .crossDissolve
        self.present(addPopUpView, animated: true, completion: nil)
    }
}
// 위임자를 본인(AddVC)로 설정하고 프로토콜의 메서드를 여기서 구현
extension AddViewController: AddPopUpViewControllerDelegate {
    func sendedDataFromPopUp() {
        viewModel.fetchData()
        DispatchQueue.main.async { [weak self] in
            self?.tableView.reloadData()
        }
    }
}

-> delegate를 addVC로 설정하고, popupVC에서 버튼을 누르면 addVC에서 구현한 프로토콜의 메서드를 작동하도록 하였다.

<< 실행 결과 >>

delegate를 설정함에도 불구하고, 위임자가 누구인지 인식을 못하는듯 하다..

빼먹은게 있는가 코드를 확인해보고, 델리게이트 패턴의 과정을 되짚어보았다..

1. 프로토콜 구성 

2. 데이터 보내는곳에서 delegate 선언 형식은 프로토콜

3. 데이터 보내는 버튼에서 프로토콜의 메서드 동작

4. 데이터 받는곳에서 delegate 위임자 지정

5. 프로토콜을 상속받아 메서드의 세부동작 구현

분명히 이대로 했는데 왜 위임자를 인식하지 못할까?

생각해낸 것들

1. 메모리 주소가 다르다(아마 유력)

클래스는 참조형식이다.

delegate 위임자를 선언하기위해(self) delegate가 선언된 뷰컨을 객체로 생성할 것이다.

또한 popupVC로 가기위해 popupvc객체를 생성했다.

결론적으로 popupVC객체를 두개를 만들었지만, 두개의 메모리 주소는 다르다.

// AddViewController.swift
class AddViewController: UIViewController {
	private var popupvc = AddPopUpViewController() // popupVC 객체 생성 1
	private func bindings() {
       popupvc.delegate = self
    }
    
    @objc func addCategory() {
        let addPopUpView = AddPopUpViewController()	// popupVC 객체 생성 2
        addPopUpView.delegate = self
        addPopUpView.modalPresentationStyle = .overFullScreen
        addPopUpView.modalTransitionStyle = .crossDissolve
        self.present(addPopUpView, animated: true, completion: nil)
    }
}

첫번째 객체 생성했을때, 메모리 현황

두번째 객체 생성했을때, 메모리 현황

아마 첫번째 객체생성의 메모리주소는 0x1088ad400, 두번째 객체생성 메모리주소는 0x10881bc00 인것 같다.

첫번째 객체에서 delegate를 위임해줬지만

실제로 popupVC로 가는 객체의 메모리주소는 두번째이므로 delegate 위임을 인식하지 못한것같다.

present를 통해 vc를 이동했을때, 이동하기위해 생성한 객체로 delegate 선언을 해보니 프로토콜에 정의된 메서드가 실행이 되었다!