개발자 퉁이리

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 다른 bfs와 비슷하지만 이번에는 대각선까지 고려해주어야 한다. 상, 하, 좌, 우, 우상, 우하, 좌하, 좌상. 총 8개의 방향을 탐색해 방문 체크해주었다. 그리고 reset() 함수를 직접 만들어주어 결괏값을 출력하면 계속 리셋해주고 반복해주었다. ⊙ ..

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 ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS로 접근하여 문제를 풀었다. 1. 값을 입력받으면 대칭적으로 '1' 값 저장 2. 1부터 시작, queue에 '1' 값 넣고 방문 표시, 반복 3. N까지 반복하는데 방문을 안 했다면 count..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS 알고리즘 돌리고 T만큼 반복해야하니 reset()이라는 초기화 함수를 만들어줬다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 51 int M,N,K; int arr[MAX][MAX]={0,}; int vi..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 코드를 다 짰는데 계속 정답 값이 안 나와 애먹은 문제다. BFS로 풀었다. 간단한 문제다. map을 입력받고 1의 값이 들어가면 queue에 push 한다. 그리고 1이 들어간 값들을 BFS를 돌린다. 그리고 방문을 안 한 곳이 있다면 days변수에 -1값을 ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS나 DFS 둘 중 아무거나 사용해도 상관없다. 이번 문제에서 퉁이리는 BFS를 이용해 풀었다. BFS로 count 값을 올려주었다. 단지가 끝나면 count 값을 result vector에 넣어준다. 그리고 이중 for문이 모두 끝나면 result vecto..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS를 사용하여 1과 연결된 모든 컴퓨터에 대해서 count를 올려주었다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 101 int n,m; int cnt=0; int arr[MAX][MAX]; bool..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 너비 우선 탐색인 BFS를 이용하여 문제를 접근했다. dx와 dy의 int 배열을 만들어 상하좌우로 움직일 수 있게 하였고 범위를 벗어나지 않으면 계속하여 탐색하도록 설계했다. pair 를 사용하였는데 first, second인 두 변수를 저장할 수 있는 struct이다. 이차원 배열의 미로에서 사용하기 위한..

https://www.acmicpc.net/problem/1260 ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 DFS와 BFS 알고리즘을 사용하여 푸는 문제이다. DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색이다. DFS의 구현은 스택 또는 재귀 함수로 구현한다. BFS의 구현은 큐를 이용해서 구현한다. ⊙ 문제 풀이 #include #include using namespace std; int n,m,v; int arr[1001][1001]; bool visit[1001]; void reset_visit() { for (auto i=1;i y; arr[x][y]=1; arr[y][x]=1; } reset_v..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 오늘 스터디에서 공부한 BFS를 적용해서 풀었다. BFS는 Breadth First Search이다. 넓이 우선 탐색, 그래프 탐색 중 하나이다. 가장 짧은, 가장 빠른과 같은 것을 물어보면 BFS를 생각하자. 그리고 파이썬에서 queue는 반드시 deque를 사용..