알고리즘/문제풀이 - 백준

백준 16236 아기 상어

문제 : https://www.acmicpc.net/problem/16236 서론 BFS문제. 아이디어 현재 위치에서 가장 가까운 물고기를 찾아야 하므로 BFS를 실행한다. 조건에 맞게 물고기를 먹고 BFS를 빠져나온 후, 물고기를 먹은 위치에서 BFS를 다시 실행하기를 반복한다. 가장 가까운 물고기가 여러마리일 경우, 가장 위의 물고기를 먹고 가장 위의 물고기가 여러마리면 가장 왼쪽의 물고기를 먹어야한다. 우선 BFS를 실행했을때 물고기를 먹고 바로 BFS를 빠져나오는게 아닌 동일한 거리의 물고기는 모두 벡터에 넣고 빠져나온다. 이를 위해 1초 후 이동할 것들은 제외한 큐의 사이즈만큼만 반복하고 BFS를 빠져나온다. while(!q.empty()){ qSize = q.size(); while(qSize..

2019. 9. 28. 11:57
알고리즘/문제풀이 - 백준

백준 17144 미세먼지 안녕!

문제 : https://www.acmicpc.net/problem/17144 서론 시뮬레이션문제. 풀이 1. 총 진행과정 지도 생성 while(time> R >> C >> T; for (int i = 0; i > map[i][j]; if (map[i][j] == -1) purifierY = i; } } } void diffusion(int y, int x) { int dy[4] = { -1,1,0,0 }; int dx[4] = { 0,0,-1,1 }; int cnt = 0; for (int i = 0; i = 0 &..

2019. 9. 27. 15:25
알고리즘/문제풀이 - 백준

백준 17143 낚시왕

문제 : https://www.acmicpc.net/problem/17143 서론 비교적 쉬운 시뮬레이션 문제. 그러나 구현은 오래걸린 문제. 아이디어 1. 지도 생성 먼저 지도를 만들어야한다. 각 상어의 정보를 상어가 위치한 칸에 입력시킨다. 이때 지도의 칸을 구조체 벡터로 만들어서 상어 정보를 입력시킨다. 구조체로 만드는 이유는 상어의 정보(s,d,z,moved)를 포함하기 위함이고(moved는 후술) 벡터로 만드는 이유는 각 칸에 여러마리의 상어가 들어갈 수 있도록 하기 위함이다. (같은 칸에 상어가 여러마리면 한마리만 살아남는데, 싸우기 직전 상황을 만들기 위함) 2. 낚시 강태공이 오른쪽으로 한칸 이동하면 그 열에서 가장 위의 상어를 먹는다. 상어가 있는지는 벡터.size()>0 을 이용하면 되..

2019. 9. 26. 22:43
알고리즘/문제풀이 - 백준

백준 17140 이차원 배열과 연산

문제 : https://www.acmicpc.net/problem/17140 서론 시뮬레이션 문제. 시뮬레이션 문제는 지문을 꼼꼼히 읽고 처음부터 실수가 없는것이 중요하다. 아이디어 R연산과 C연산을 구현하는게 핵심이다. R연산을 예로 들어서 1. 배열의 모든 행에서 각 행마다 어떤 숫자가 몇개인지 체크하기 위해서 check 배열을 만들어준다. 어떤 행이 [1,2,1] 일 때 check[1]++; check[2]++; check[1]++; 해주면 check배열값은 0,2,1,0,0,....로 check[1] = 2, check[2] = 1 처럼 어떤 값이 몇개인지 알 수 있다. 2. 각 행에서 어떤 숫자가 몇개인지 알아냈다면 그것을 정렬해야한다. 1이 두개, 2가 하나면 [2,1,1,2]로 정렬해야한다...

2019. 9. 26. 16:21
알고리즘/문제풀이 - 백준

백준 9370 미확인 도착지

문제 : https://www.acmicpc.net/problem/9370 서론 최단경로 문제이므로 다익스트라로 접근했다. 이 문제는 풀이 아이디어가 두개다 하나는 다익스트라를 두번 사용하는 방법이고 또 다른 하나는 다익스트라를 세번 사용하는 방법이다. 테스트케이스가 여러개라서 매번 간선을 초기화해줘야하는데 초기화하는 부등호를 H->T S->H->G->T 두가지다. 즉 목적지 후보 T에 대해 S->T까지의 최단거리 = S->G까지의 최단거리 + G->H까지의 최단거리 + H->T까지의 최단거리 가 성립하거나 S->T까지의 최단거리 = S->H까지의 최단거리 + H->G까지의 최단거리 + G->T까지의 최단거리 가 성립하면 간선 GH를 포함한 최단경로를 통해 도착한 것이므로 출력하면 된다. 그리고 위의 조..

2019. 8. 29. 22:29
알고리즘/문제풀이 - 백준

백준 2580 스도쿠

문제 : https://www.acmicpc.net/problem/2580 서론 정답이 여러개가 나오면 전부 출력을 하는 문제가 있었는데, 발견이 쉽지 않았다. 다른분들의 코드에서 'exit(0)'을 발견하고 알아낼 수 있었다. 풀이 이 문제는 DFS 문제다. 처음 만나는 0의 좌표에 1~9까지 각각 넣어보고 조건에 맞으면 두번째 만나는 0도 1~9까지 넣어보고 이를 반복하다가 마지막에 만나는 0도 1~9까지 중 하나를 넣었더니 답을 만족하면 출력한다. 만약 두번째 만나는 0을 1~9까지 전부 넣어봤는데 조건에 맞는게 없다면 첫번째 만난 0에서 값을 잘못 넣은 것이므로 리턴하는 방식이다. 조건은 3개가 주어지는데 셋 다 함수로 만들고 리턴값은 boolean으로 줬다. 세 함수의 리턴값이 전부 true면 ..

2019. 8. 28. 22:01