Category: BFS

0

백준 1012 - 유기농 배추 (Python)

백준 1012 - 유기농 배추 (Python)링크https://www.acmicpc.net/problem/2606 전체 소스 코드def bfs(y, x): q = [] q.append([y, x]) check[y][x] = True while q: cntY, cntX = q.pop() for i in range(4): ny = cntY + dy[i] nx = cntX + dx[i] if 0 > ny or ny >= col or 0 > nx or nx >= row: continue if check[ny][nx] == False and field[ny][nx] == 1: q.append([ny, nx]) check[ny][nx] = Truetest_case = int(input())row = 0col = 0k = 0field = []check = []dy = [1, -1, 0, 0]dx = [0, 0, 1, -1]for t in range(test_case): row, col, k = map(int, input().split()) field = [[0] * row for _ in range(col)] check = [[False] * row for _ in range(col)] count = 0 for i in range(k): x, y = map(int, input().split()) field[y][x] = 1 for i in range(col): for j in range(row): if check[i][j] == False and field[i][j] == 1: count += 1 bfs(i, j) print(count)

0

백준 2606 - 바이러스 (Python)

백준 2606 - 바이러스 (Python)링크https://www.acmicpc.net/problem/2606 전체 소스 코드def bfs(start_node): q = [] q.append(start_node) check[start_node] = True count = 0 while q: node = q.pop(0) for i in range(1, node_num+1): if check[i] == False and field[node][i] == 1: q.append(i) count += 1 check[i] = True return countnode_num = int(input())line_num = int(input())field = [[0]*(node_num+1)for i in range(node_num+1)]check = [False]*(node_num+1)for i in range(line_num): a, b = map(int, input().split()) field[a][b] = 1 field[b][a] = 1print(bfs(1))

0

백준 2606 - 단지번호 붙이기 (Python)

백준 2667 - 단지번호 붙이기 (Python)링크https://www.acmicpc.net/problem/2667 전체 소스 코드def bfs(y, x): q = [] q.append([y, x]) check[y][x] = True count = 0 while len(q) > 0: count += 1 cntY = q[0][0] cntX = q[0][1] q.pop(0) for i in range(4): ny = cntY + dy[i] nx = cntX + dx[i] if 0 > ny or ny >= n or 0 > nx or nx >= n: continue if check[ny][nx] == False and field[ny][nx] != 0: check[ny][nx] = True q.append([ny, nx]) values.append(count)dy = [1, -1, 0, 0]dx = [0, 0, 1, -1]n = int(input())color = 0values = []check = [[False] * n for i in range(n)]field = [[0] * n for i in range(n)]for i in range(n): line = input() for j in range(len(line)): field[i][j] = int(line[j])for i in range(n): for j in range(n): if check[i][j] == False and field[i][j] != 0: color += 1 bfs(i, j)values.sort()print(color)for i in values: print(i)

0

백준 14592 - 연구소

백준 14592 - 연구소https://www.acmicpc.net/problem/14592 문제풀이해당 문제에서는 3가지 입력 N, M, 지도 모양이 주어진다. N : 세로 크기 M : 가로 크기 지도 정보 지도 내 상태는 3가지 상태가 존재한다. 0 : 빈칸 1 : 벽 2 : 바이러스 알고리즘 실행계획은 다음과 같이 진행한다. 벽을 세운다. 바이러스 확산 시킨다. 바이러스 영역을 확인한다.

0

백준 2178 - 미로탐색

링크https://www.acmicpc.net/problem/2178 문제 풀이기본적인 BFS 문제다. 조건에 맞춰 값을 읽어온 후 탐색을 진행하면 원하는 값을 얻을 수 있다. 전체 소스import java.io.BufferedReader;import java.io.IOError;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class Main { public static int height, width; public static int[] dx = { 0, 0, 1, -1 }; public static int[] dy = { 1, -1, 0, 0 }; public static int[][] map; public static int bfs() { Queue<int[]> q = new LinkedList<>(); boolean check[][] = new boolean[height + 1][width + 1]; q.offer(new int[] { 0, 0 }); check[0][0] = true; int count = 0; while (!q.isEmpty()) { int qSize = q.size(); count++; while (qSize-- > 0) { int[] point = q.remove(); int cntY = point[0]; int cntX = point[1]; if (cntY == height - 1 && cntX == width - 1) { return count; } for (int i = 0; i < 4; i++) { int nY = cntY + dy[i]; int nX = cntX + dx[i]; if (0 <= nY && nY < height && 0 <= nX && nX < width) { if (check[nY][nX] == false && map[nY][nX] == 1) { check[nY][nX] = true; q.offer(new int[] { nY, nX }); } } } } } return count; } public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] inputValues = br.readLine().split(" "); height = Integer.parseInt(inputValues[0]); width = Integer.parseInt(inputValues[1]); map = new int[height + 1][width + 1]; for (int h = 0; h < height; h++) { String inputValue = br.readLine(); for (int w = 0; w < width; w++) { // System.out.println(inputValue.charAt(w)); map[h][w] = inputValue.charAt(w) - '0'; } } int count = bfs(); System.out.println(count); br.close(); }}

0

1194-달이차오른다_가자

백준 1194 - 달이 차오른다. 가자https://www.acmicpc.net/problem/1194 문제 해설기존 BFS문제를 푸는 형식에 비트마스킹까지 더해진 문제이다. 비트마스킹을 통해 키를 가지고 있는 각각의 상태들을 체크할 수 있다. 키는 총 6개가 주어지기 때문에 50x50x64 = 160,000 의 공간 복잡도를 갖게 돼 메모리 제한에 걸리지 않는다. 소스 코드#include <bits/stdc++.h>using namespace std;int N, M;char Map[55][55];bool check[1 << 6][55][55];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};queue<pair<int, int>> q;int startY, startX;struct point { int y; int x; int key; int count;};int bfs() { queue<point> q; q.push({startY, startX, 0, 0}); check[0][startY][startX] = true; while (!q.empty()) { int cntY = q.front().y; int cntX = q.front().x; int cntKey = q.front().key; int cntCount = q.front().count; q.pop(); if (Map[cntY][cntX] == '1') { return cntCount; } for (int i = 0; i < 4; i++) { int ny = cntY + dy[i]; int nx = cntX + dx[i]; if (0 >= ny || ny > N || 0 >= nx || nx > M) { continue; } if (check[cntKey][ny][nx] == true) { continue; } if (Map[ny][nx] == '.') { check[cntKey][ny][nx] = true; q.push({ny, nx, cntKey, cntCount + 1}); } else { // 열쇠에 마주쳤을 경우 if ('a' <= Map[ny][nx] && Map[ny][nx] <= 'f') { int key = (1 << (Map[ny][nx] - 'a')); check[cntKey | key][ny][nx] = true; q.push({ny, nx, cntKey | key, cntCount + 1}); } // 문을 만났을 경우 if ('A' <= Map[ny][nx] && Map[ny][nx] <= 'F') { int door = (1 << (Map[ny][nx] - 'A')); if (door & cntKey) { check[cntKey][ny][nx] = true; q.push({ny, nx, cntKey, cntCount + 1}); } } // 출구를 만났을 경우 if (Map[ny][nx] == '1') { q.push({ny, nx, cntKey, cntCount + 1}); } } } } return -1;}void init() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { cin >> Map[i][j]; if (Map[i][j] == '0') { startY = i; startX = j; Map[i][j] = '.'; } } }}int main(void) { cin >> N >> M; init(); cout << bfs() << '\n'; return 0;}

0

백준 3190 - 뱀

https://www.acmicpc.net/problem/3190 체점 현황 전체 소스 코드#include <bits/stdc++.h>using namespace std;int board[110][110];int board_size;int num_of_apple;int num_of_command;map<int, char> command;// 동, 남, 서, 북int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};int direction[4] = {0, 1, 2, 3};struct snake { int y; int x; int dir;};int main(void) { cin >> board_size >> num_of_apple; for (int i = 0; i < num_of_apple; i++) { int y, x; cin >> y >> x; board[y][x] = 1; } cin >> num_of_command; for (int i = 0; i < num_of_command; i++) { int time; char dir; cin >> time >> dir; command[time] = dir; } queue<pair<int, int>> snake_tail; int snake_head_y = 1; int snake_haed_x = 1; int snake_dir = 0; snake_tail.push({1, 1}); board[1][1] = 2; int time = 0; while (true) { time++; snake_head_y += dy[snake_dir]; snake_haed_x += dx[snake_dir]; snake_tail.push({snake_head_y, snake_haed_x}); if (board[snake_head_y][snake_haed_x] == 2) { cout << time << '\n'; return 0; } if (0 >= snake_head_y || snake_head_y > board_size || 0 >= snake_haed_x || snake_haed_x > board_size) { cout << time << '\n'; return 0; } if (board[snake_head_y][snake_haed_x] == 1) { board[snake_head_y][snake_haed_x] = 2; } else { board[snake_head_y][snake_haed_x] = 2; board[snake_tail.front().first][snake_tail.front().second] = 0; snake_tail.pop(); } if (command.find(time) != command.end()) { char com = command[time]; command.erase(time); if (com == 'L') { snake_dir = (snake_dir + 3) % 4; } else { snake_dir = (snake_dir + 1) % 4; } } } return 0;}

0

백준 1726 - 로봇

링크https://www.acmicpc.net/problem/1726 채점 현황 전체 소스 코드#include <iostream>#include <queue>using namespace std;int M, N;int map[101][101];bool check[101][101][4];int dx[4] = {0, 1, -1, 0};int dy[4] = {-1, 0, 0, 1};// char dir[4] = { 'N', 'E', 'W', 'S' };struct point { int y; int x; int dir;};int main(void) { cin >> M >> N; for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { cin >> map[i][j]; } } point start, goal; int tempY, tempX, tempD; cin >> tempY >> tempX >> tempD; start.y = tempY; start.x = tempX; start.dir = tempD % 4; cin >> tempY >> tempX >> tempD; goal.y = tempY; goal.x = tempX; goal.dir = tempD % 4; queue<point> q; q.push(start); check[start.y][start.x][start.dir] = true; int num = 0; while (!q.empty()) { int q_size = q.size(); while (q_size--) { int y = q.front().y; int x = q.front().x; int d = q.front().dir; q.pop(); if (y == goal.y && x == goal.x && d == goal.dir) { cout << num << '\n'; return 0; } int nextR, nextL; if (d == 0) { nextR = 1; nextL = 2; } else if (d == 1) { nextR = 3; nextL = 0; } else if (d == 2) { nextR = 0; nextL = 3; } else if (d == 3) { nextR = 2; nextL = 1; } if (check[y][x][nextR] == false) { check[y][x][nextR] = true; q.push({y, x, nextR}); } if (check[y][x][nextL] == false) { check[y][x][nextL] = true; q.push({y, x, nextL}); } for (int i = 1; i <= 3; i++) { int nx = x + dx[d] * i; int ny = y + dy[d] * i; if (1 <= ny && ny <= M && 1 <= nx && nx <= N) { if (map[ny][nx] == 1) { break; } if (check[ny][nx][d] == false) { check[ny][nx][d] = true; q.push({ny, nx, d}); } } } } num++; // for (int i = 1; i <= M; i++) { // for (int j = 1; j <= N; j++) { // cout << check[i][j][3] << " "; // } // cout << endl; // } // cout << endl; }}

0

백준 1600 - 말이 되고픈 원숭이

링크https://www.acmicpc.net/problem/1600 체점 현황 문제 풀이 말처럼 뛸 수 있는 횟수(k), width, height를 입력 받는다. field에 대한 정보를 입력 받는다. (0, 0)에서 시작해 (width-1, height-1)까지 갈 수 있는 최소 횟수를 탐색한다. 원숭이가 움직일 수 있는 방법은 두가지가 존재한다. 말처럼 뛸 수 있는 방법(k내의 횟수에서) 상하좌우로 움직일 수 있는 방법 말이 (width-1, height-1)에 도착하면 그 횟수를 반환한다. 만약 도착하지 못할 경우 -1을 반환한다. 말이 움직인 횟수를 출력해준다. 전체 소스 코드#include <bits/stdc++.h>using namespace std;int numOfKnight;int width, height;int field[202][202];bool check[31][202][202];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};int horse_dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};int horse_dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};struct point { int k; int y; int x;};int bfs(int y, int x) { check[0][y][x] = true; queue<point> q; q.push({0, y, x}); int count = 0; while (!q.empty()) { int q_size = q.size(); while (q_size--) { int cntK = q.front().k; int cntY = q.front().y; int cntX = q.front().x; q.pop(); if (cntY == height - 1 && cntX == width - 1) { return count; } if (cntK < numOfKnight) { for (int i = 0; i < 8; i++) { int ny = cntY + horse_dy[i]; int nx = cntX + horse_dx[i]; if (0 > ny || ny >= height || 0 > nx || nx >= width) continue; if (field[ny][nx] == 0 && check[cntK + 1][ny][nx] == false) { check[cntK + 1][ny][nx] = true; q.push({cntK + 1, ny, nx}); } } } for (int i = 0; i < 4; i++) { int ny = cntY + dy[i]; int nx = cntX + dx[i]; if (0 > ny || ny >= height || 0 > nx || nx >= width) continue; if (field[ny][nx] == 0 && check[cntK][ny][nx] == false) { check[cntK][ny][nx] = true; q.push({cntK, ny, nx}); } } } count++; } return -1;}int main(void) { cin >> numOfKnight >> width >> height; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { cin >> field[i][j]; } } int minValueOfMove = bfs(0, 0); cout << minValueOfMove << '\n'; return 0;}