본문 바로가기

BFS11

BOJ 11559 - Puyo Puyo(DFS, BFS, 배열 조작, 구현) C++, Java 풀이 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net - 전형적인 구현 문제이지만 생각보다 정확하고 빠르게 풀기 힘들었던 문제이다. 한 턴에 연쇄가 여러 번 일어나도 1연쇄로 카운트 되므로 한 턴에 모든 연쇄에 대해서 처리한 다음 블럭을 아래로 내리면 된다. C++은 dfs, Java는 bfs로 풀이하였다. #include #include #include #include #include using namespace std; .. 2022. 3. 23.
프로그래머스 고득점 Kit 하루만에 뽀개기 - 8. 깊이/너비 우선검색(DFS,BFS) C++ 풀이 https://programmers.co.kr/learn/courses/30/parts/12421 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - java풀이와 C++풀이가 거의 차이점이 없어서 C++ 풀이로만 정리하였다 1. 타겟 넘버 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 .. 2022. 3. 19.
BOJ 16973 - 직사각형 탈출(BFS, 부분합) https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net - 이문제에서 부분합을 쓰지 않고 직사각형 내부에 벽이 있는지 검사하는 로직을 쓰면 복잡도가 O(WH)인 연산을 맵의 모든 칸에서 한번씩 돌게 되므로 O(NMWH) = 1000^4 연산을 하게 되서 시간 초과가 난다. - 1차원 부분합 개념을 통해서 i~j까지의 합을 s[j] - s[i] 로 표현할 수 있는데 2차원 부분합도 이와 유사하게 구현할 수 있다. - 1. (1,.. 2022. 2. 13.
[boj]16236 - 아기상어(BFS, 우선순위 큐) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net - 조건에 먹이를 먹는 조건의 우선순위가 정해져있다. (1. 아기상어 위치에서 가까운 순 2. 가장 위 3. 가장 왼쪽). 이를 other.x; } return d > other.d; } }; int n, size = 2, exp = 0, ans = 0; int a[20][20]; int check[20][20]; priority_queue pq; void bfs() { while (!pq.. 2021. 7. 2.

티스토리툴바