본문 바로가기

분류 전체보기

 (89)
백준 2178번 미로 탐색 https://www.acmicpc.net/problem/2178 아이디어:1. 입력받을 때, string tmp로 입력받고 이중 for문으로 for(auto x : tmp) board[i][j] = x - '0'; 로 board 배열 입력2. BFS의 방문을 검사하는 배열인 vis[101][101]에 방문 여부인 bool형이 아닌 해당 위치까지의 거리 int형을 기록vis[nx][ny] = vis[cur.first][cur.second] + 1; #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() { ..
백준 1926번 그림 https://www.acmicpc.net/problem/1926 아이디어:1. 문제의 핵심은 BFS를 시작하는 지점을 큐에 넣어주는 것이중 for문으로 board[i][j] == 1 && vis[i][j] == 0 을 검사해서 큐 push(), vis[i][j] 체크, tmp_area++, num++2. BFS 과정은 동일하고 큐에서 pop() ~ 인접 지역 큐에 push() 하는 과정에서 tmp_area++3. 한 그림이 끝났을 때 area = max(area, tmp_area) 로 최대 넓이 계산 #include #include using namespace std;int board[501][501];int vis[501][501];int dx[4] = { 1, 0, -1, 0 };int dy[4] ..
넓이우선탐색 BFS 넓이우선탐색, BFSBreadth-First Search다차원 배열이나 그래프에서 각 칸을 탐색할 때 너비를 우선으로 탐색하는 알고리즘 큐 사용모든 노드 확인 O(n) 탐색 순서는 아래부터 반시계 방향 순서x = 행y = 열  7행 10열 탐색 코드#include #include using namespace std;int board[502][502] ={ {1,1,1,0,1,0,0,0,0,0}, {1,0,0,0,1,0,0,0,0,0}, {1,1,1,0,1,0,0,0,0,0}, {1,1,0,0,1,0,0,0,0,0}, {0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0} };bool vis[502][502];int n = 7, m = 10..
백준 3986번 좋은 단어 https://www.acmicpc.net/problem/3986 아이디어:1. string tmp로 입력받고 for (auto x : tmp)로 순회한다.2. stack3. 스택이 비어있지않고 x와 top()이 같은 글자라면 pop()4. 그렇지 않다면 push()5. 마지막에 스택이 비어있으면 ans++ #include #include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, ans = 0; cin >> N; while (N--) { string tmp; stack S; cin >> tmp; for (auto x : tmp) { if (!S.empty() && S.top(..
백준 4949번 균형잡힌 세상 https://www.acmicpc.net/problem/4949 아이디어:1. 입력받을 때 string tmp; getline(cin, tmp);로 한줄 입력 받고 각 글자에 auto i로 접근하여 괄호 문자인지 체크2. tmp == "." 이면 반복문 종료3. 닫는 괄호가 나왔을 때, 여는 괄호가 없어 pop() 할 수 없다면 그냥 스택에 넣고 마지막에 스택 비어있는지만 체크 if문 사용하는 정갈한 코드#include #include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); string str; while (1) { getline(cin, str); if (str == ".") break; ..

티스토리툴바