백준 문제풀이(BOJ PS)

문제 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 어떤 문제인가? 빈칸, 벽, 바이러스 총 세 종류로 맵을 채울 수 있다. 이때, 임의의 벽을 추가로 3개 세운다. 추가로 세운 벽의 위치에 따라 안전한 공간의 개수가 바뀐다. 임의의 벽을 세웠을 때 안전한 공간의 최대 개수를 출력하면 된다. 접근 방법 코드를 먼저 보면 복잡하고 이해하기 어려울 것 같으니 대략적인 문제풀이의 방향을 보고 코드를 보자! 1. map에 입력받기 이때, 바이러스의 위치와 빈..

문제 : https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 어떤 문제인가? 이 문제는 기존의 2차원에서 움직이던 그래프 탐색이 아니라 3차원으로 이동해야 한다. 시작 좌표 S부터 움직여가며 도착 좌표 E까지 이동하는 게 걸리는 시간을 출력하면 된다. 접근 방법 int dx[6] = {1, -1, 0, 0, 0, 0}; int dy[6] = {0, 0, 1, -1, 0, 0}; int dz[6] = {0, 0, 0, 0, 1, -1}; 위의 배열들은 x..

문제 : https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 어떤 문제인가? 입력을 받으면 땅인 부분과 바다인 부분이 생긴다. 한 땅 덩어리가 하나의 연결 요소라고 생각하면 된다. 이때 연결 요소 내에서 한 정점에서 다른 정점으로 가는 최대 거리를 출력하면 되는 것이다. 접근 방법 int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; 한 정점에서 상, 하, 좌, 우로 움직이기 위한 배열이다. char map[..

문제 : https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 어떤 문제인가? 아주 간단한 문제이다. 기존의 상, 하, 좌, 우로 그래프를 탐색하던 방법에서 나이트의 이동 방식처럼만 움직이며 탐색하면 되는 문제이다. 나이트의 시작 위치와 도착 위치가 주어졌을 때 도착하는 최소 횟수를 출력하면 된다. 접근 방법 int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[8] = {1, -1, 2, -2, 2, -2, 1, -..

문제 : https://www.acmicpc.net/problem/1325 > n >> m; 문제에서 주어진 변수를 선언하고 입력받는다. while (m--) { int a, b; cin >> a >> b; graph[b].push_back(a); } 간선의 개수인 m번만큼 한 간선이 연결하는 두 정점을 입력받는다. 이때, 단방향 그래프임에 유의하여 b정점에 연결된 정점으로 a를 추가해준다. int maxNum = 0; vectorans; for (int i = 1; i maxNum){ maxNum=cnt; ans.clear(); ans.push_back(i); } else if(cnt ==maxNum){ ans.push_back(i); } for (int j = 0; j

문제 : https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 어떤 문제인가? 존재하는 정점들 중 한 정점에서 다른 모든 정점으로 가는 거리들을 모두 더한 값을 케빈 베이컨 수라고 한다. 이때, 케빈 베이컨수가 가장 작은 정점의 번호를 출력하면 된다. 접근 방법 먼저 정점 간의 거리를 측정해야 하기 때문에 bfs를 사용하기로 했다. vector graph[5001]; bool visited[101]; ..

문제 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 어떤 문제인가? 입력된 그래프를 탐색해나가며 모든 토마토가 익는데 걸리는 최소 날짜를 출력하는 문제이다. 접근 방법 int tomato[1001][1001]; bool visited[1001][1001]; int n, m; 토마토 상자의 값을 저장할 이차원 배열과 방문 여부를 저장할 이차원 배열, n과 m을 선언해준다. queue q; 탐색에 필요한 큐를 선언해준다. 이때..

문제 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 어떤 문제인가? 각 위치의 높이가 존재한다. 따라서, 0부터 최대 높이까지 모든 경우를 살펴봐야 한다. 잠기는 높이마다 생기는 연결 요소들의 개수가 바뀌게 된다. 이때, 어떤 높이에서 생기는 연결 요소의 최대 개수를 출력하면 된다. int map[101][101]; bool visited[101][101]; int n; 위치들의 높이를 저장할 이차원 배열과 방문 여부를 저장할 이차원 배열, n을..

문제 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 어떤 문제인가? 그래프를 입력받고 연결 요소의 개수를 출력하면 된다. 이 문제를 풀기위해선 먼저 연결 요소가 무엇인지 알아야 한다. 간단하게 말하면 나누어진 각각의 그래프들을 연결 요소라고 한다. 문제의 첫 번째 예시대로 입력을 받으면 1-2-5, 3-4-6이 연결된 두 개의 연결 요소가 존재하는 것이다. 접근 방법 한 정점을..

문제 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 어떤 문제인가? n*m 크기의 공간에서 0과 1로 미로를 만든다. 1은 지나갈 수 있고 0은 지나갈 수 없는 곳이다. 이때 왼쪽 위부터 출발해 오른쪽 아래까지 갈 수 있는 최소 거리를 구하면 된다. 접근 방법 이동의 가중치가 없는 그래프에서 최단 경로를 구하는 것이기 때문에 bfs를 통해 접근하였다. int miro[101][101]; bool visited[101][101]; 먼저 미로를 저장할 이차원 배열과 방문처리..