본문 바로가기

algorithm

 (69)
백준 6593번 상범 빌딩 https://www.acmicpc.net/problem/6593 아이디어:1. 3차원 BFS2. board[z][x][y], int dz[6] = { 1, -1, 0, 0, 0, 0 }; int dx[6] = { 0, 0, 1, 0, -1, 0 }; int dy[6] = { 0, 0, 0, 1, 0, -1 };, int nz, nx, ny 순서에 주의3. tuple 사용 #include #include using namespace std;char board[31][31][31];int vis[31][31][31];int dz[6] = { 1, -1, 0, 0, 0, 0 };int dx[6] = { 0, 0, 1, 0, -1, 0 };int dy[6] = { 0, 0, 0, 1, 0, -1 };int m..
백준 2468번 안전 영역 https://www.acmicpc.net/problem/2468 아이디어:1. BFS 순환에 조건 추가2. 1~100 순환보다 더 적게하기 위해 높이 중 최소값과 최대값을 구하여 그 사이에서 순환3. board[i][j] 4. 영역 개수의 최대값을 출력 #include #include using namespace std;int board[101][101];int vis[101][101];int dx[4] = { 1, 0, -1, 0 };int dy[4] = { 0, 1, 0, -1 };int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); queue> Q; int n, tmp, ans = 0, maxi = 0, mini = 100; cin >>..
백준 5014번 스타트링크 https://www.acmicpc.net/problem/5014 아이디어:1. 1697번 숨바꼭질과 같은 2차원 BFS 문제2. Q.pop() 하면서 cur == G인지 검사하고 출력3. vis[2000001]은 해당 층에 도달하기 까지 누른 버튼 횟수 (미로의 넓이와 동일)4. 이동할 때 U는 +로, D는 -로 표현5. 0층은 존재하지 않으므로 continue, 최대층(F)을 넘기면 continue #include #include using namespace std;int vis[2000001];int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int F, S, G, U, D; cin >> F >> S >> G >> U >> D; int ..
백준 2583번 영역 구하기 https://www.acmicpc.net/problem/2583 아이디어:1. 직사각형 k에 대해 board[i][j] = 1 로 하고 2중 for문으로 board[i][j] == 0 && vis[i][j] == 0 을 찾아 큐에 넣으면서 BFS2. 큐에 넣으면서 num++; 넓이로 저장할 area는 큐에서 빼면서 ++한 뒤, area가 0이 아닐 때 벡터 areas에 삽입3. 벡터 areas를 sort()로 정렬해서 num 뒤에 출력 n과 m이 각각 y축, x축을 가리 키는 것에 주의y축에서, 그림을 상하 반전 시켜도 넓이는 그대로이므로문제 그림에 충실해서 for문을 반대로 돌리는 등 별도 처리하지 않아도 된다. #include #include using namespace std;char board[..
백준 5427번 불 https://www.acmicpc.net/problem/5427 아이디어:1. 4179번 불! 을 여러번 수행하는 문제2. bool 형 isPossible을 두어 반복문의 끝에 "IMPOSSIBLE" 출력 여부 검사 #include #include using namespace std;char board[1001][1001];int vis[1001][1001];int fire[1001][1001];int dx[4] = { 1, 0, -1, 0 };int dy[4] = { 0, 1, 0, -1 };int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int n, m; cin >> m >> ..

티스토리툴바