본문 바로가기

BFS3

[백준] 16236번 : 아기상어 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제를 2덩어리로 나눠서 생각하면 편한 문제이다. 현재 위치에서 어디로 가야할 지 찾는 부분(bfs(shark_x, shark_y, v, shark_size) 함수가 담당. 이거는 최악의 경우 n^2 시간이 걸림. 최악의 경우 배열의 모든 원소를 다 따져봐야 하는 경우도 있으니까) 그리고 이차원 배열의 모든 원소의 위치마다 그 경우를 따져야 하니까(main함수의 while문에서 담당). 그것도 최악의 경.. 2021. 1. 1.
[백준] 7569번 : 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net //C++ #include #define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; typedef long long ll; int m, n, h, notomato = 0; int dir[6][3] = { {0,1,0},{0,-1,0},{1,0,0},{-1,0,0},{0,0,1},.. 2020. 8. 22.
[백준] 2667번 : 단지 번호 붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net #include using namespace std; int n; int house[26][26] = { 0 }; int danji_max[1000]; //index 1을 1단지로 하기! index 1부터 출력! int danji_index = 0; int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; //한 점으로 부터의 UP,DOWN,RIGHT,LEFT int i.. 2020. 6. 21.