BFS19 [백준 5427] 불 www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net bfs 응용문제이다. "불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. " -> 불이 먼저 이동한다는 말이다. 불을 먼저 이동시킨다음에 상근이가 배열을 벗어날 수 있다면 탈출! #include #include #include using namespace std; int t, w, h; int src_x, src_y; char arr[1001][1001]; int person_visited[1001][100.. 2020. 12. 3. [leetcode 210] Course Schedule II There are a total of n courses you have to take labelled from 0 to n - 1. Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai. Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses. If there are many valid answe.. 2020. 11. 16. [백준 13913] 숨바꼭질 4 www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS후에 경로까지 추적하는 문제이다. BFS할때마다 경로를 저장하면 시간초과가 난다. 따라서 마지막 목적지에 도달했을 때 경로를 역추적해야 한다. 경로 역추적을 위해 부모노드를 저장했다. #include #include #include #define MAX 100000 + 1 using namespace std; int path[MAX] = { 0, }; int parent[.. 2020. 11. 1. [백준 1600] 말이 되고픈 원숭이 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net - 3차원 배열 bfs문제였다. - 처음엔 2차원 배열로 했다가 틀렸다. 3차원으로 해야 하는 이유는 말을 통해서 가는 거리와 원숭이가 가는 거리를 분리해줘야 하기 때문이다. 말을 이용해서는 목적지까지 도착을 못한다고 가정해보자. (원숭이만을 이용해서 갈 수 있다고 가정) 2차원 배열에 path를 등록하여 이미 지나간 거리를 지나가지 않는다면 도착지까지 도달하지 못할 것이다. 그래서 말을 사용했.. 2020. 10. 29. 이전 1 2 3 4 5 다음