본문 바로가기

algorithm

 (69)
백준 4179번 불! https://www.acmicpc.net/problem/4179 아이디어:1. 불에 대한 BFS와 지훈이에 대한 BFS를 따로 진행2. 'F'를 모두 찾고 거리(= 시간)를 기록하는 BFS 수행3. J를 찾고 'F' 도착시간보다 늦거나 같이 도착하는 경우, 이미 불이 지나간 경우를 검사하면서 거리(= 시간)를 기록하는 BFS 수행4. J의 BFS 도중 범위를 벗어나면 탈출한 것으로 거리(= 시간)를 출력하며 종료 초기 'J'의 위치가 i = 0, i = n - 1, j = 0, j = m - 1인 경우일 때 바로 return하는 풀이 #include #include using namespace std;char board[1001][1001];int vis[1001][1001];int fire[1001]..
백준 7576번 토마토 https://www.acmicpc.net/problem/7576 아이디어:1. 시작지점이 여러 곳인 BFS큐에 한번에 넣어놨다가 for문으로 큐에 있는걸 전부 pop()하면서 BFS 수행하고 ans++2. 입력 n, m이 반대인 것에 주의3. 큐에 시작지점을 넣으면서 ans에 1이 추가되는 것에 주의, 따라서 ans = -1로 설정4. 이중 for문으로 시작지점으로 있는 1을 모두 큐에 push()5. Q.size()를 변수 s에 별도로 저장하여 for(int i = 0; i 그렇지 않다면 BFS를 수행하며 Q에 다시 push()한 만큼 size()가 변경돼 반복을 더 수행한다.6. 익은 토마토는 board[nx][ny]에 별도 표시7. BFS를 끝내고 이중 for문으로 board를 순회하면서 안익은 ..
백준 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..

티스토리툴바