1389번 - 케빈 베이컨의 6단계 법칙

문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다. 케빈 베이..

• format_list_bulleted Problem Solving/C++
• · 2023. 7. 23.
• textsms

21736번 - 헌내기는 친구가 필요해

문제 입력 출력 첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다. 문제 풀이 해당 문제는 너비 우선 탐색으로 풀이를 진행한다 자세한 설명은 코드의 주석으로 설명 코드 #include #include using namespace std; const int MAX = 601; int M, N; // 가로 세로 bool visit[MAX][MAX]; // 방문여부 char input[MAX][MAX]; // 입력받는 문자 확인 int dy[] = { 1,-1,0,0 }; int dx[] = { 0,0,1,-1 }; int ans; // 만날 수 있는 사람의 숫자 queue q; void BFS() { while (!q.empty()) { int x = q..

• format_list_bulleted Problem Solving/C++
• · 2023. 7. 22.
• textsms

1541번 - 잃어버린 괄호

문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 풀이 방법 0으로 시작하는 숫자가 있으며, ‘-’ 연산자를 만난 후의 모든 숫자를 뺀 값이 최소값이 ..

• format_list_bulleted Problem Solving/C++
• · 2023. 7. 22.
• textsms

1260번 - DFS와 BFS

문제 입출력 풀이 DFS - 깊이 우선 탐색 BFS - 너비 우선 탐색 #include #include using namespace std; int N, M, V; // 정점개수, 간선개수, 시작정점 int map[1001][1001]; // 인접 그래프 bool visited[1001]; // 방문 여부 queue q; void reset() { for (int i = 1; i > a >> b; map[a][b] = 1; map[b][a] = 1; } reset(); DFS(V); cout

• format_list_bulleted Problem Solving/C++
• · 2023. 7. 17.
• textsms

7576번 - 토마토

문제 입출력 풀이 너비 우선 탐색을 통해 최소 날짜 구하기 입력받은 토마토에서 익지 않는 것이 있을 경우 -1 출력 입력받은 토마토가 이미 모두 익어있으면 0 출력 → -1이 입력되면 이미 방문한것으로 취급하여 너비 우선 탐색 진행 #include #include using namespace std; const int MAX = 1001; int M, N; // 가로 세로 int map[MAX][MAX]; // 최단 거리 저장 bool visit[MAX][MAX]; // 방문했는지 확인 int input[MAX][MAX]; // 처음 입력받는 토마토 상태 int dy[] = { 1,-1,0,0 }; int dx[] = { 0,0,1,-1 }; queue q; void BFS() { while (!q.em..

• format_list_bulleted Problem Solving/C++
• · 2023. 7. 10.
• textsms

14940번 - 쉬운 최단거리

1. 문제 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라. 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자. 2. 입력 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다. 3. 출력 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 4. 풀이 1) 입력이 2인 지점을 초기 위치로 설정 2) BFS를 통해 초기 위치로 부터 최단 거리 구하기..

• format_list_bulleted Problem Solving/C++
• · 2023. 7. 7.
• textsms