Little cabin in the woods

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/4803📌 문제 탐색하기목표그래프가 주어졌을 때, 트리의 개수를 세기입력[첫 줄] 정점의 개수 n (n ≤ 500) , 간선의 개수 m (m ≤ n(n-1)/2 )[둘째 줄 ~ m+1 줄 (m개의 줄)] 간선을 나타내는 두개의 정수 * 같은 간선은 여러 번 주어지지 않는다.* 정점은 1번  ~ n 번 까지의 번호* 입력의 마지막 줄에는 0이 두 개 주어진다.  출력그래프에 트리가 없다면 : No trees트리가 한 개라면 : There is one tree트리가 T개 라면 : A forest of T trees. ( 테스트케이스 번호 : 적절한 문장 ) 형식으로 출력해야 함.예시 > Case 1 : A forest ..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/1012📌 문제 탐색하기목표각 테스트 케이스에 대해 필요한 배추흰지렁이의 최소 마리 수 출력하기해야 할 것배추밭 정보를 어떤 형태로 저장할까?인접한 배추밭 묶음의 개수를 어떻게 구할까?입력[첫줄] 테스트 케이스의 개수 T[ 각 테스트 케이스의 첫째 줄] 배추 밭의 가로길이 M ( 1≤M≤50), 배추밭의 세로길이 N( 1≤N≤50 ), 배추가 심어져 있는 위치의 개수 K ( 1 ≤ K ≤ 2500 )[ 각 테스트 케이스의 둘째줄 ~ K+1 줄 ] 배추의 위치 좌표 X, Y (  0 ≤ X ≤ M-1 , 0 ≤ Y ≤ N-1 )아이디어1. 배추밭 정보를 어떤 형태로 저장할까? 배추 밭의 가로 길이 = 열의 수 = M배..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/1697📌 문제 탐색하기목표수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하기해야 할 것1. 수빈이와 동생의 위치 정보를 어떤 형태로 저장할까?2. 수빈이가 동생을 어떻게 찾을까?입력[첫줄] 수빈이의 위치 N, 동생의 위치 K ( 0 ≤ N, K ≤ 10^5 )아이디어1. 수빈이와 동생의 위치 정보를 어떤 형태로 저장할까?( 문제를 다 풀고 다시 생각해보니, 그냥 0~ 10^5 숫자이기 때문에 굳이 따로 저장할 필요가 없었다.) 수빈이가 걸을 때 : 앞 뒤로 한칸 움직일 수 있고수빈이가 순간이동 하면 : 앞으로 두배만큼 간다 수빈이가 있는 현재 위치를 X라고 할..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/4179📌 문제 탐색하기목표지훈이가 미로에서 탈출할 수 있는지 구하고, 탈출하기 위해 걸리는 최소 시간 출력하기해야 할 것1. 지훈이가 탈출할 수 있는 지점이 어딘지 파악하기2. 지훈이가 각 지점으로 이동하는데에 걸리는 시간 구하기3. 불이 각 지점으로 이동하는데에 걸리는 시간 구하기4. 지훈이가 탈출할 수 있는 지점까지 불보다 빨리 이동할 수 있는지 구하기입력[첫줄] R ( 미로 행의 개수 ) , C ( 열의 개수 ), 1 ≤ R, C ≤ 1000 [둘째줄 ~ R+1줄] 미로 정보#: 벽.: 지나갈 수 있는 공간J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)F: 불이 난 공간아이디어1. 지훈이가 탈출할 ..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/7576📌 문제 탐색하기목표전체 토마토가 익는데 걸리는 최소 일수 구하기(만약 토마토가 모두 익지 못하는 상황이면 -1 출력하기)해야 할 것1. 토마토를 어떤 식으로 저장해야할까?2. 모든 토마토가 익는데 걸리는 시간을 어떻게 계산할까?입력[첫줄] 상자의 가로 크기 : M, 세로 크기 : N (  2 ≤ M,N ≤ 1,000 )[둘째줄 ~ N+1줄] 토마토 정보아이디어1. 토마토를 어떤 식으로 저장해야할까?➡️N*M 의 크기를 가진 2차원 배열로 저장하자.➡️익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 들어 있지 않은 칸은 -1 의 값을 가진다. 2. 모든 토마토가 익는데 걸리는 시간을 어떻게 계산할까?10..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/2178📌 문제 탐색하기목표(1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸의 수 구하기 (시작위치와 도착위치도 칸을 셀 때 포함할 것)해야 할 것1. 미로의 정보를 어떤 식으로 저장할까?2. 이동해야 하는 최소 칸 수를 어떻게 구하지?입력[첫줄] 행의 개수 : N , 열의 개수 : M ( 2 ≤ N, M ≤ 100 )[둘째줄 ~ n+1줄] 미로아이디어1. 미로의 정보를 어떤 식으로 저장할까?➡️N행 M열의 2차원 배열로 저장한다.int[][] map = new int[N][M];➡️해당 칸의 상,하,좌,우 에 인접한 1이 있으면 그 칸(노드)은 연결된 것으로 치는 일종의 그래프로 이해할 수..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/1926 이 문제를 통해 BFS 알고리즘 구현 연습을 해보도록 하자.📌 문제 탐색하기목표그림의 개수와, 그림의 넓이 중 최대값 출력하기해야 할 것1. 그림의 정보를 어떤 식으로 저장할까?2. 그림의 개수, 넓이를 어떻게 알 수 있을까?입력[첫줄] 도화지의 세로 크기 n(1 ≤ n ≤ 500), 가로 크기 m(1 ≤ m ≤ 500) [둘째줄 ~ n+1줄] 그림의 정보아이디어1. 그림의 정보를 어떤 식으로 저장할까? 이 문제는 n*m개의 노드가 주어지고, 어떤 노드들끼리 이어졌는지 확인하라는 문제로 해석할 수 있다.2차원배열 int[n][m] 을 사용해 각 셀의 상태 (1 또는 0)을 저장하도록 하자. 2. 그림의 개수..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/5567 📌 문제 탐색하기목표상근이가 결혼식에 초대할 사람의 수 구하기해야 할 것친구 관계를 어떻게 저장할까?상근이와 2 개 간선 이내로 연결된 동기는 총 몇명인지 구하기입력n : 전체 동기의 수 ( 2 ≤ n ≤ 500 ) = 정점의 개수m : 리스트의 길이 = 관계의 개수 = 간선의 개수  ai bi : 친구 관계 쌍 = 간선아이디어 친구 관계를 어떻게 저장할까?딕셔너리를 활용한 인접 리스트 ( 0번 인덱스에는 [] 저장하기 )상근이와 연결된 동기는 총 몇 명인지 구하기 상근이(1번)를 시작 노드로 하여, BFS 로 탐색 진행  ➡️ 2개의 간선 이내로 방문 가능해야 한다는 조건이 있기 때문에 최단거리를 보장하는 ..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/2606  📌 문제 탐색하기목표1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수 출력하기해야 할 것컴퓨터의 네트워크 관계를 어떻게 저장할까?1번 컴퓨터와 연결되어 있는 컴퓨터를 어떻게 탐색할까?입력컴퓨터의 수 ( 1 이상, 100 이하 )연결된 컴퓨터 쌍의 수 ( = 간선의 수 )컴퓨터 1, 컴퓨터 2 형태로 간선이 주어짐아이디어컴퓨터의 네트워크 관계를 어떻게 저장할까? 컴퓨터 == 정점, 컴퓨터 쌍 == 간선딕셔너리를 활용한 인접 리스트 ( 0번 인덱스에는 [] 저장하기 )1번 컴퓨터와 연결되어 있는 컴퓨터를 어떻게 탐색할까? DFS 또는 BFS로 탐색하기 ➡️ 나는 BFS 이용BFS 탐색을 통해 도달할 수..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/1260 📌 문제 탐색하기목표그래프를 DFS와 탐색한 결과와 BFS로 탐색한 결과 출력하기해야 할 것DFS 함수 구현하기BFS 함수 구현하기입력N : 정점의 개수 ( 1 ≤ N ≤ 1,000 )M : 간선의 개수 (1 ≤ M ≤ 10,000) V : 탐색을 시작할 정점의 번호( 정점, 정점 ) 으로 간선 나열아이디어DFS 는 재귀를 활용해서 구현하고, BFS는 deque을 활용해서 구현해봐야겠다.그래프는 { 정점1 : [] , 정점1 : [] }  형식의 인접리스트로 저장하자.방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하기! ➡️정점 1 : [] value에 오는 리스트를 오름차순 정렬..