7569. 토마토 문제 풀이 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 지난번에 푼 토마토 판이 3D가 된 문제. 메인 로직은 별로 차이가 없었고, y와 x뿐만이 아니라 z값까지 queue에 보관해주었다. 인접해있는 사방뿐만이 아니라 위 아래까지 비교했다. 비교 배열 int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; >> int dx[6] = { 0,1,0,-1,0,0 }; int dy[6] = { 1, 0,-1,0,0,0 }; int d..
1260. 토마토 문제 풀이 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 토마토 전염병이 모두 퍼지는 최소 일수를 구하는 문제. 자료구조 시간에 배웠던 BFS로 풀 수 있었다. 알고리즘 설계 입력받을 때 이미 익은 토마토의 좌표(y, x)를 queue에 넣어준다. 이 때 익지 않은 토마토의 전체 개수를 센다. queue가 empty가 될 때까지 현재 queue의 top에 인접한 좌표(사방)에 토마토들을 모두 익은 상태로 만들어준다.그리고 익힌 토마토의 개수를 센다. 이..
14940. 쉬운 최단 거리 문제 풀이 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 모든 지점까지의 최단경로를 구하는 문제. 전에 풀었던 토마토 문제와 미로 찾기 문제처럼 BFS를 사용해서 푸는 문제이다. 알고리즘 시작 위치를 queue에 넣는다. queue가 빌 때까지 while문을 돌린다. queue의 top에 사방에 인접해있는 것들이 방문되지 않은 곳이고, 갈 수 있는 길이라면 queue에 넣는다. 사방을 탐색했다면, queue를 pop한 다음에 다음 좌표를..
2667. 단지번호붙이기 문제 풀이 > len; for (int i = 0; i > str; for (int j = 0; j < len; j++) { field[i][j] = (str[j] == '1'); } } // DFS for (int y = 0; y < len; y++) { for (int x = 0; x < len; x++) { if (!visited[y][x] && field[y][x]) { // 방문 횟수를 우선순위 큐에 넣음 pQueue.push(DFS(y, x)); } } } // 사이즈 출력 cout
1325. 효율적인 해킹 문제 풀이 > cnt >> len; for (int i = 0; i > a >> b; m[b].push_back(a); } for (int i = 1; i
1260. DFS와 BFS 문제 풀이 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 기본적인 DFS, BFS 문제였다. DFS는 재귀함수를 사용해서, BFS는 queue를 사용해서 구현했다. 알고리즘 DFS 재귀함수로 start를 매개변수로 넣어 호출한다. 인자로 들어온 start를 방문했음을 bool 배열에서 체크해준다. 1부터 정점의 수까지 방문하지 않았고, 인접한 정점을 재귀함수로 호출해준다. void DFS(int start) { visited[start] = t..
2606. 바이러스 문제 풀이 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 재귀를 사용한 DFS로 푼 문제. 연결되어있는 컴퓨터들은 전부 바이러스에 걸리기 때문에 인접행렬을 사용해 DFS로 인접한 노드들을 타고 타고 들어가서 체크를 해주었다. 1부터 시작해서 각 정점을 방문할 때마다 count 변수를 1씩 증가시켜주었다. 코드 #include using namespace std; bool arr[101][101]; bool visited[101]; int cnt, len, answer; void DFS(int ..
6497. 전력난 문제 풀이 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 기본적인 MST 문제였다. 전체 비용 - MST의 비용이 절약할 수 있는 최대 비용이기 때문이다. 알고리즘 설계 간선을 입력받으며 간선들과 간선들의 모든 가중치를 더해 저장한다. 간선들을 가중치 기준으로 오름차순 정렬한다. union-find와 memoization을 사용해 사이클이 생기지 않게 크루스칼 알고리즘을 이용해 MST의 비용을 구한다. 모든 간선의 가중치의 합 - MST 비용을 출력한다. 코드 #include using namespa..
