강위찬

재미있는 SW이야기를 소개합니다.

wichan.dev@gmail.com
https://github.com/wichan7

[programmers] 아이템 줍기

업데이트:

programmers lv3. 아이템 줍기

1차

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

class Queue {
    constructor() {
        this._arr = [];
    }
    enqueue(e) {
        return this._arr.push(e);
    }
    dequeue() {
        return this._arr.shift();
    }
    isEmpty() {
        this._arr.length === 0 ? true : false;
    }
}

function printMap(map) {
    for (let i = 0; i < 50; i++) {
        for (let j = 0; j < 50; j++) {
            process.stdout.write(map[i][j] + "");
        }
        process.stdout.write("\n");
    }
}

function createMap() {
    let array = [];
    for (let i = 0; i < 50; i++) {
        let inner = [];
        for (let j = 0; j < 50; j++) {
            inner.push(0);
        }
        array.push(inner);
    }
    
    return array;
}

function fill(map, rect) {
    let x1 = rect[0];
    let y1 = rect[1];
    let x2 = rect[2];
    let y2 = rect[3];
    
    for (let i=x1; i<=x2; i++) {
        for (let j=y1; j<=y2; j++) {
            map[j][i] = 1;
        }
    }
}

function isValid(map, posY, posX) {
    const x1 = posX - 1;
    const y1 = posY - 1;
    const x2 = posX + 1;
    const y2 = posY + 1;

    if (map[posY][posX] === 0) {
        return false;
    }

    for ( let i = x1; i <= x2; i++ ) {
        for (let j = y1; j <= y2; j++ ) {
            if ( map[j][i] === 0 ) {
                return true;
            }
        }
    }

    return false;
}

function solution(rectangle, characterX, characterY, itemX, itemY) {

    //init
    let map = createMap();
    let visited = createMap();
    for (let rect of rectangle) {
        fill(map, rect);
    }
    map[itemY][itemX] = 2;

    //bfs queue
    let q = new Queue();
    
    visited[characterY][characterX] = 1;

    //init characterPos and enqueue
    if (isValid(map, characterY-1, characterX)) {
        //go top
        q.enqueue([characterY-1, characterX, 2]);

    }
    if (isValid(map, characterY, characterX+1)) {
        //go right
        q.enqueue([characterY, characterX+1, 2]);

    }
    if (isValid(map, characterY+1, characterX)) {
        //go bottom
        q.enqueue([characterY+1, characterX, 2]);

    }
    if (isValid(map, characterY, characterX-1)) {
        //go left
        q.enqueue([characterY, characterX-1, 2]);
    }

    //bfs start
    while (!q.isEmpty()) {
        let [y, x, cnt] = q.dequeue();
        visited[y][x] = cnt;
        cnt += 1;

        if (map[y][x] === 2) {
            return visited[y][x];
        }

        if (isValid(map, y-1, x) && visited[y-1][x] === 0) {
            //go top
            q.enqueue([y-1, x, cnt]);

        }
        if (isValid(map, y, x+1) && visited[y][x+1] === 0) {
            //go right
            q.enqueue([y, x+1, cnt]);

        } 
        if (isValid(map, y+1, x) && visited[y+1][x] === 0) {
            //go bottom
            q.enqueue([y+1, x, cnt]);

        }
        if (isValid(map, y, x-1) && visited[y][x-1] === 0) {
            //go left
            q.enqueue([y, x-1, cnt]);

        }
    }

}

위 코드로 해결이라고 생각했는데 예측치보다 최단거리가 적게 나왔다.

도저히 이유를 모르겠어서 검색해봤더니.. 테스트케이스 1번에서 P(3, 5) P(3, 6) 발생하는 반례가 있었다.

반례 해결을 위해 맵 사이즈를 *2 하더라.

조금만 더 생각해볼걸.. 해결 실패 ㅠㅠ

댓글남기기

참고