문제링크 : https://www.acmicpc.net/problem/4179


아이디어

  • BFS를 사용해서 지훈이와 불을 각각 하나씩 이동해주자
  • 이떄 지훈이가 밖으로 넘어가면 종료

시간복잡도 계산

  • BFS(V+E)
    • V : O(RC)
    • E : O(RC*4)
    • 총합 : O(RC)

자료구조

  • map[1000][1000]
  • BFS queue<pair<int, int>>
    • 좌표 최대 1000
  • 시간 t : 최대 1000

코드(C++)

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
#include <iostream>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
char map[1010][1010];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    queue<pi2> jihoon;
    queue<pi2> fire;
    
    int R,C; cin >> R >> C;
    for(int j=0; j<R; j++) {
        for(int i=0; i<C; i++) {
            cin >> map[j][i];
            if(map[j][i] == 'J') jihoon.push(make_pair(j,i));
            else if(map[j][i] == 'F') fire.push(make_pair(j,i));
        }
    }
    
    int t=0;
    while(1) {
        t++;
        // 지훈 먼저 이동
        int jsize = jihoon.size();
        if(jsize == 0) break;
        
        while(jsize--) {
            auto ej = jihoon.front(); jihoon.pop();
            int ey = ej.first;
            int ex = ej.second;
            
            // 만약 현재 위치가 불이라면 이동불가
            if(map[ey][ex] == 'F') continue;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                // 탈출하면 종료
                if(!(ny>=0 && ny < R && nx >=0 && nx < C)) {
                    cout << t << '\n';
                    return 0;
                }
                
                // .일떄만 이동
                if(map[ny][nx] == '.' ) {
                    map[ny][nx] = 'J';
                    jihoon.push(make_pair(ny, nx));
                }
            }
            
        }
        
        // 불 이동
        int fsize = fire.size();
        while(fsize--) {
            auto ef = fire.front(); fire.pop();
            int ey = ef.first;
            int ex = ef.second;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
 
                if(ny>=0 && ny < R && nx >=0 && nx < C) {
                    if(map[ny][nx] == 'J' || map[ny][nx] == '.') {
                        map[ny][nx] = 'F';
                        fire.push(make_pair(ny, nx));
                    }
                }
            }
        }
        
        
        
    }
    
    cout << "IMPOSSIBLE";
    
    return 0;
}
 
cs

문제유형

  • BFS - 경찰과 도둑
    • 경찰은 쫓고, 도둑은 탈출
    • bfs로 맵을 인자로하면 메모리 차지가 너무크므로, 경찰, 도둑 좌표를 인자로

'알고리즘 > 백준' 카테고리의 다른 글

백준 15649 N과 M (1)  (0) 2021.03.15
백준 2579 계단 오르기  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14

문제링크 : https://www.acmicpc.net/problem/4485


아이디어

  • 최소비용으로 목적지에 도착해야함 >> 다익스트라
  • 다익스트라 알고리즘 내에서 간선을 통해서 이동한 값이 더 작을경우 갱신

시간복잡도 계산

  • 다익스트라 알고리즘 : O(ElgE)
    • 여기서 E : N^2 * 4
    • O(N^2 * lg N^2)

자료구조

  • 현재 거리값 dist : 최대값 N^2 * 10 = 2e5
  • 전체 지도 map : 최대값 10

코드(C++)

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
#include <iostream>
#include <queue>
#include <tuple>
 
using namespace std;
typedef tuple<int, int, int> ti3;
 
int dist[150][150];
int map[150][150];
const int inf = 3e5;
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=0;
    while(1) {
        
        fill(&dist[0][0], &dist[149][150], inf);
        
        int N; cin >> N;
        if(N==0) break;
        
        for(int j=0; j<N; j++) {
            for(int i=0; i<N; i++) {
                cin >> map[j][i];
            }
        }
        
        priority_queue<ti3, vector<ti3>, greater<ti3>> pq;
        
        // 출발점
        dist[0][0] = map[0][0];
        pq.push({dist[0][0], 0, 0});
        
        while(!pq.empty()) {
            int ec, ey, ex;
            tie(ec,ey,ex) = pq.top(); pq.pop();
            
            if(dist[ey][ex] != ec) continue;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                if(ny >= 0 && ny < N && nx >= 0 && nx < N) {
                    if(dist[ny][nx] > dist[ey][ex] + map[ny][nx]) {
                        dist[ny][nx] = dist[ey][ex] + map[ny][nx];
                        pq.push({dist[ny][nx], ny, nx});
                    }
                }
            }
        }
        
        t++;
        cout << "Problem " << t << ": " << dist[N-1][N-1] << '\n';
    }
    
    
    return 0;
}
cs

문제유형

  • 2차원 다익스트라
    • 목적지 도착하는데 최소 비용 문제
    • 현재 비용 표시되는 배열 추가해서, 현재보다 작으면 업데이트

'알고리즘 > 백준' 카테고리의 다른 글

백준 2579 계단 오르기  (0) 2021.03.14
백준 4179 불!  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13

문제링크 : https://www.acmicpc.net/problem/1926


아이디어

  • BFS 사용해서 연결된 노드 구하기(Flood Fill)
    • 전체 노드 순회하면서 체크 안되어있는 노드 발견할경우 BFS 수행
      • 이떄마다 전체 그림 카운트 수 증가
      • 그리고 그림 가장 넓은값 구하기

시간복잡도 계산

  • BFS : O(V+E)
    • V : 모든 노드수 : O(NM)
    • E : 노드에서 간선수 4방향 : O(4NM)
    • N과 M 최대값이라고 가정시
    • 총합 : O(5N^2)
      • O(5*N^2) = 5 * 25e4 : 125e4 = 1.25e6

자료구조

  • 그림 개수 cnt : 최대 N^2 = 25e4 : INT 가능
  • 그림 최대 크기 maxv : 최대 N^2 = 25e4 : INT 가능
  • BFS에서 사용하는 큐 queue<pair<int, int>>

코드(C++)

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
#include <iostream>
#include <queue>
 
using namespace std;
 
int map[510][510];
bool chk[510][510];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int N,M;
 
int bfs(int y, int x) {
    int cnt=0; // 그림 크기
    
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    chk[y][x] =1;
    
    while(!q.empty()) {
        auto eq = q.front(); q.pop();
        int ey = eq.first;
        int ex = eq.second;
        cnt++; // 그림 크기 증가
        
        for(int k=0; k<4; k++) {
            int ny = ey + dy[k];
            int nx = ex + dx[k];
            if(ny>=0 && ny < N && nx>=0 && nx < M) {
                if(map[ny][nx] == 1 && chk[ny][nx] == 0) {
                    chk[ny][nx] = 1;
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }
    
    return cnt;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&chk[0][0], &chk[509][510], 0);
    
    cin >> N >> M;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    
    int cnt=0;
    int maxv= 0;
    
    // 체크되어있지 않은 경우 bfs 수행
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            if(map[j][i] == 1 && chk[j][i] == false) {
                maxv = max(maxv, bfs(j,i));
                cnt++;
            }
        }
    }
    
    cout << cnt << '\n';
    cout << maxv << '\n';
    
    
    return 0;
}
 
cs

문제유형

  • BFS - Flood Fill
    • 이어져있는 노드를 연결하는 문제
    • BFS 사용해서, 이어져 있는 노드 확인

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 4179 불!  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13
백준 1747 소수&팰린드롬  (0) 2021.03.13

+ Recent posts

티스토리툴바