그래프 (1) 최근 푼 문제

아니,,블로그 정리를 어떻게 해야할지 모르겠다.

 

15559 내 선물을 받아줘

15886 내 선물을 받아줘2

2536 버스 갈아타기

5214 환승

 

---

15559 내 선물을 받아줘 → union find (Disjoint Set)

15886 내 선물을 받아줘2 → 문자열 내 EW의 개수

 

 

 

 

---

2536 버스 갈아타기 → BFS

가로/세로로 움직이는 버스를 나누어

갈아탈 수 있는 버스를 찾아내는 방법을 생각해낼 것

 

 

 

bfs

 

ver[N] ver[ i ] = x=i에서 세로로 움직이는 버스들 저장

hor[N] hor[ i ] = y=i에서 가로로 움직이는 버스들 저장

vis[N] vis[ i ] = i번째 버스를 타기까지 갈아탄 최소 횟수 

int bfs() {
    // STEP 1. 시작점을 포함하는 버스
    for (info b : ver[SX]) {
        if (b.s <= SY && SY <= b.e) vis[b.n] = 1, Q.push(b.n);
    }
    for (info b : hor[SY]) {
        if (b.s <= SX && SX <= b.e) vis[b.n] = 1, Q.push(b.n);
    }

    // STEP 2. BFS
    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();

        int x1 = B[cur].x1, y1 = B[cur].y1;
        int x2 = B[cur].x2, y2 = B[cur].y2;

        if (y1 == y2) {
        //IF) Horizontal - 교차하는 Vertical or 겹치는 Horizontal
            if (y1 == DY && DX >= x1 && DX <= x2) return vis[cur];
            
            for (int x = x1; x <= x2; ++x)
                for (info b : ver[x]) {
                    if (vis[b.n] || y1 < b.s || y1 > b.e) continue;
                    
                    vis[b.n] = vis[cur] + 1; Q.push(b.n);
                }
            for (info b : hor[y1]) {
                if (vis[b.n] || x2 < b.s || x1 > b.e) continue;
                
                vis[b.n] = vis[cur] + 1; Q.push(b.n);
            }
        }
        else {          
        //IF) Vertical - 교차하는 Horizontal or 겹치는 Vertical 
            if (x1 == DX && DY >= y1 && DY <= y2) return vis[cur];
            
            for (int y = y1; y <= y2; ++y) {
                for (info b : hor[y]) {
                    if (vis[b.n] || x1 < b.s || x1 > b.e) continue;

                    vis[b.n] = vis[cur] + 1; Q.push(b.n);
                }
            }
            for (info b : ver[x1]) {
                if (vis[b.n] || y2 < b.s || y1 > b.e) continue;

                vis[b.n] = vis[cur] + 1; Q.push(b.n);
            }
        }
    }
}

 

---

5214 환승 → BFS

hypertube를 vertex로 생각