본문 바로가기

알고리즘/BFS

 (5)
백준 17142 연구소 3 1. 연구소에 비활성 바이러스 5개가 존재하고 3개를 활성시킬시 5개에서 3개를 뽑는 경우의 수를 다 구해야 한다.(dfs로 구현했다) 2. 3개를 선정후 각 사항에 맞게 몇시간후에 바이러스가 연구소를 차게 하는지 bfs를 통해 계산한다. - 여기서 유의 사항에 주목해야 하는데 중요한건 '비활성 바이러스'를 벽으로 보면 안된다는 거다. 즉 다 채우고 비활성바이러스가 나머지 항목에 있으면 끝내줘야 한다. 비활성바이러스쪽으로 들어가면서 시간을 더 투자해선 안된다. 해결방법은 처음에 감염시켜야 할 연구소방의 갯수를 기억하고 나중에 비교한다. (처음 한 방법은 한번 탐색할때마다 전체 염구소를 탐색해서 끝났는지 확인하는건데 이 경우는 너무 많은 시간을 소비하는 별로인 알고리즘이였다.) 3. 위치를 변경하고 계산해..
백준 11403 경로 찾기 #include #include #include using namespace std; int N; int Map[100][100]; int result[100][100]; bool visit[100]; queue q; void Calc() { for (int i = 0; i < N; i++) { for (int q = 0; q < N; q++) { visit[q] = 0; } for (int j = 0; j < N; j++) { visit[i] = true; if (Map[i][j] == 1) { q.push(j); result[i][j] = 1; } } while (!q.empty()) { int current_po = q.front(); q.pop(); for (int k = 0; k < N; k++..
백준 1012번 유기농배추. #include #include #include using namespace std; typedef struct { int position_x; int position_y; }earth_bug; int test_case; int N, M, K; bool visit[51][51]; int x, y; int Map[51][51]; int result; int dirx[4] = { 0,0,-1,1 }; int diry[4] = { 1,-1,0,0 }; queue q; void Input() { scanf("%d", &test_case); for (int i = 0; i < test_case; i++) { for (int c = 0; c < 51; c++) { for (int y = 0; y < 51; y++)..
백준 2667 단지 번호 #include #include #include using namespace std; typedef struct { int position_x; int position_y; }apartment; int Map[25][25]; bool visit[25][25]; int N; queue q; priority_queue pq; int dirx[4] = {0,0,1,-1}; int diry[4] = {-1,1,0,0}; void Input() { scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%1d", &Map[i][j]); } } } void Calc() { for (int i = 0; i < N; i++)..
백준 7576 토마토 그냥 눈대중으로 풀었다. 첫번째로 푼것 : #include #include #include #include #include using namespace std; typedef struct { int position; int time; }tomato; int M, N; int Map[1000][1000]; queue q; int min_count; int dirx[4] = { 0,0,1,-1 }; int diry[4] = { -1,1,0,0 }; clock_t start, endi; void Input() { scanf("%d %d", &M, &N); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &Map[i][j]); if..

티스토리툴바