ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] #1953 _ 탈주범 검거
    Problem Solving/SWEA 2019. 10. 29. 16:29

    [탈주범 검거] https://swexpertacademy.com/main/code/problem/problemDetail.do

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

    bfs를 이용하여 지하 터널의 시간 별 갈 수 있는 곳을 모두 구해준 후,

    해당 시간 내에 갈 수 있는 곳의 개수를 세는 방법으로 구현하였다.

     

    이때, 1번 터널 구조물 오른쪽에 2번 터널 구조물이 있는 경우에는 갈 수 없다.

    이와 같이 현재 위치에서는 갈 수 있더라도,

    갈 위치의 구조물의 형태를 파악해 갈 수 있는지 없는지 고려해야 한다.

     

    [ 소스 코드 ]

    #include <cstdio>
    #include <queue>
    #include <algorithm>
    #define MAX 50
    
    using namespace std;
    
    int dx[] = { 0, 1, 0, -1 }, dy[] = { -1, 0, 1, 0 };
    int N, M, R, C, L;
    int map[MAX][MAX], chk[MAX][MAX];
    
    void initChk();
    int solve();
    void bfs(int y, int x);
    int main() {
    	int T;
    	scanf("%d", &T);
    	for (int i = 1; i <= T; i++) {
    		scanf("%d %d %d %d %d", &N, &M, &R, &C, &L);
    		for (int j = 0; j < N; j++) {
    			for (int k = 0; k < M; k++) {
    				scanf("%d", &map[j][k]);
    			}
    		}
    
    		initChk();
    
    		printf("#%d %d\n", i, solve());
    	}
    
    	return 0;
    }
    
    void initChk() {
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < M; j++) chk[i][j] = 0;
    	}
    }
    
    int solve() {
    	int cnt = 0;
    
    	bfs(R, C);
    
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < M; j++) {
    			if (chk[i][j] == 0) continue;
    			if (L < chk[i][j]) continue;
    			cnt++;
    		}
    	}
    
    	return cnt;
    }
    
    void bfs(int y, int x) {
    	int tmp_x, tmp_y, s, e;
    	queue<pair<int, int> > q;
    	pair<int, int> tmp;
    
    	q.push(make_pair(y, x));
    	chk[y][x] = 1;
    
    	while (!q.empty()) {
    		tmp = q.front();
    		q.pop();
    		if (chk[tmp.first][tmp.second] < L) {
    			switch (map[tmp.first][tmp.second]) {
    			case 4: s = 0; e = 2; break;
    			case 5: s = 1; e = 3; break;
    			case 6: s = 2; e = 4; break;
    			case 7: s = 3; e = 5; break;
    			default: s = 0; e = 4; break;
    			}
    
    			for (int i = s; i < e; i++) {
    				if ((map[tmp.first][tmp.second] == 2) && (i % 2 == 1)) continue;
    				if ((map[tmp.first][tmp.second] == 3) && (i % 2 == 0)) continue;
    
    				tmp_x = tmp.second + dx[i % 4];
    				tmp_y = tmp.first + dy[i % 4];
    
    				if (tmp_x < 0 || tmp_y < 0 || tmp_x >= M || tmp_y >= N) continue;
    				if (map[tmp_y][tmp_x] == 0) continue;
    				if (chk[tmp_y][tmp_x] != 0) continue;
    
    				if (i % 4 == 0) { //up
    					if (map[tmp_y][tmp_x] == 3 || map[tmp_y][tmp_x] == 4 || map[tmp_y][tmp_x] == 7) continue;
    				}
    				else if (i == 1) { //right
    					if (map[tmp_y][tmp_x] == 2 || map[tmp_y][tmp_x] == 4 || map[tmp_y][tmp_x] == 5) continue;
    				}
    				else if (i == 2) { //down
    					if (map[tmp_y][tmp_x] == 3 || map[tmp_y][tmp_x] == 5 || map[tmp_y][tmp_x] == 6) continue;
    				}
    				else { //left
    					if (map[tmp_y][tmp_x] == 2 || map[tmp_y][tmp_x] == 6 || map[tmp_y][tmp_x] == 7) continue;
    				}
    
    				q.push(make_pair(tmp_y, tmp_x));
    				chk[tmp_y][tmp_x] = chk[tmp.first][tmp.second] + 1;
    			}
    		}
    	}
    }

    'Problem Solving > SWEA' 카테고리의 다른 글

    [SWEA] #2115 _ 벌꿀채취  (0) 2019.10.29
    [SWEA] #2105 _ 디저트 카페  (0) 2019.10.29
    [SWEA] #1953 _ 탈주범 검거  (0) 2019.10.29
    [SWEA] #1952 _ 수영장  (0) 2019.10.29
    [SWEA] #1949 _ 등산로 조성  (0) 2019.10.26
    [SWEA] #4014 _ 활주로 건설  (0) 2019.08.28

    댓글 0

@Jo Grini's Blog :)