ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] #1249 _ 보급로
    Problem Solving/SWEA 2019. 7. 17. 07:00
    728x90

    [보급로] https://www.swexpertacademy.com/

     

    SW Expert Academy

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

    swexpertacademy.com

     

    처음에는 dp로 풀 수 있을 것이라고 생각하였다.

    그러나, 아래와 같이 돌아가야하는 경우에 내가 생각한 dp로 풀면 올바른 답을 얻을 수 없다.

     

    dp의 결과로는 7이 최소 시간으로 구해지나, 최소 시간은 6이다.

    이와 같은 경우를 고려하기 위해 bfs를 사용하였다.

     

    지도에서 bfs로 그냥 탐색하면 시간이 너무 오래 걸리기 때문에 불필요한 탐색은 줄여야한다.

    dp의 결과를 기준으로 두고,

    dp의 값 보다 작은 경우에만 bfs로 탐색하여 최소 시간을 구하는 방식으로 구현하였다.

    (다른 사람의 풀이를 보니 bfs를 하면서 시간이 커지면 멈추는 방식으로 한 것 같았다.)

     

    입력데이터가 띄어쓰기가 없기 때문에 문자로 한 글자씩 받아

    48 (0의 ascii 값 == 48) 을 빼줌으로써 숫자로 변환하였다.

    (찾아보니 %1d를 이용하면 1자리만 받아 숫자로 바로 입력 받는 것도 가능하다.)

     

    [ 소스 코드 ]

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #define MAX 100
    #define INF 999999
    
    using namespace std;
    int map[MAX + 1][MAX + 1] = { 0, }, n;
    int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
    
    int solve();
    int main() {
    	int test_case;
    	char input;
    
    	scanf("%d", &test_case);
    	for (int i = 1; i <= test_case; i++) {
    		scanf("%d", &n);
    		for (int j = 0; j < n; j++) {
    			for (int k = 0; k < n; k++) {
    				scanf("%c", &input);
    				if (input == '\n') scanf("%c", &input);
    				map[j][k] = input - 48;
    			}
    		}
    		printf("#%d %d\n", i, solve());
    	}
    
    	return 0;
    }
    
    int solve() {
    	queue<pair<int, int> > q;
    	pair<int, int> idx;
    	int path[MAX + 1][MAX + 1];
    	int x, y;
    
    	for (int i = 0; i < n; i++) memset(path[i], INF, sizeof(int)*n);
    
    	path[0][0] = 0;
    	for (int i = 0; i < n; i++) { //use dp
    		for (int j = 0; j < n; j++) {
    			if (i == 0 && j == 0) continue;
    			else if (i == 0) path[i][j] = path[i][j - 1] + map[i][j];
    			else if (j == 0) path[i][j] = path[i - 1][j] + map[i][j];
    			else path[i][j] = min(path[i][j - 1] + map[i][j], path[i - 1][j] + map[i][j]);
    		}
    	}
    
    	for (int i = 0; i < n; i++) { //use bfs
    		for (int j = 0; j < n; j++) {
    			q.push(make_pair(i, j));
    			while (!q.empty()) {
    				idx = q.front();
    				q.pop();
    				for (int k = 0; k < 4; k++) {
    					x = idx.second + dx[k];
    					y = idx.first + dy[k];
    					if (x < 0 || y < 0 || x >= n || y >= n) continue;
    					if (path[y][x] > path[idx.first][idx.second] + map[y][x]) {
    						q.push(make_pair(y, x));
    						path[y][x] = path[idx.first][idx.second] + map[y][x];
    					}
    				}
    			}
    		}
    	}
    	return path[n - 1][n - 1];
    }
    반응형

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

    [SWEA] #2805 _ 농작물 수확하기  (0) 2019.08.04
    [SWEA] #1215 _ 회문1  (0) 2019.08.04
    [SWEA] #5658 _ 보물상자 비밀번호  (0) 2019.07.17
    [SWEA] #1249 _ 보급로  (0) 2019.07.17
    [SWEA] #1208 _ Flatten  (0) 2019.07.10
    [SWEA] #1240 _ 단순 2진 암호코드  (0) 2019.07.03

    댓글 0

@Jo Grini's Blog