개발/백준

백준 13460번: 구슬 탈출 2

문제 링크: https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 문제 해결 방법: BFS 또는 DFS인데, 기울이기가 한 칸씩 이동개념이랑 다르다. 테스트 케이스 2번째로 한 칸씩..

백준 10451번: 순열 사이클

문제링크: https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다. 순열을 배열을 이용해 \(\begin{pmatrix} 1 www.acmicpc.net 문제 해결 방법은, 기본 DFS 방문 표시를 하면서 깊이 탐색하다보니, Main 문에서 실행되는 DFS 함수의 횟수는 순열..

백준 9466번: 텀 프로젝트

문제링크: https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r= www.acmicpc.net 처음에는 그냥 단순 DFS인줄 알았다. 순환인 그래프를 찾는 DFS였다. BOOL 배열 변수 하나 선언해서 진행했다. (사..

백준 1325번: 효율적인 해킹

문제링크: https://www.acmicpc.net/problem/1325 1325번: 효율적인 해킹 첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다. www.acmicpc.net 전형적인 DFS문제 어렵지 않다. 사실 정답률 보고, 얼마나 오래 걸릴까 걱정했는데 1시간? 30분? 이렇게 푼 것 같다. 그러나 문제를 착각할 수가 있다. A가 B를 신뢰한다 == 서로가 서로를 신뢰하다고 보면 안된다. 그래서 벡터에 넣어놓고 보면 방향성이 있는 그래프로 확인할 수 있다..

백준 1963번: 소수 경로

문제 링크: https://www.acmicpc.net/problem/1963 1963번: 소수 경로 문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야" “그럼 8179로 해” “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. www.acmicpc.net 아이디어 : 1. 에라토스테네스의 체를 통해 10000이하 소수를 구한다. 2. 한 자리 씩 바꿔가며, 소수가 가능한 경우의..

백준 1389번: 케빈 베이컨의 6단계 법칙

문제 링크: https://www.acmicpc.net/problem/1389 불러오는 중입니다... 아이디어 : 플로이드 와샬 알고리즘 의견 : 처음에는 DFS에 분류되어 있어, DFS로 풀려했는데, 도저히 안돼서 플로이드 와샬로 품. #define MAX_INF 100000 #include #include #include using namespace std; int nGraph[101][101]; int N, M; void FloydWarshall() { for (int k = 1; k > M; int nFriend1, nFriend2; for (int i = 1; i > nFriend1 >> nFriend2; nGraph[nFriend2][nFriend1] = 1; nGraph[nFriend1][n..

백준 11724번: 연결 요소의 개수

문제 링크: 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 아이디어 : DFS 이것은 정점 기준으로 방문체크해주면서, Main 문에서 실행 한 DFS 카운트 횟수를 계산하는 것이 포인트. 의견 : BFS를 풀고 싶어서 찾은건데, DFS로 푸는 것이 맞다 생각했다. 그리고 DFS 기본 구현을 하면 풀 것 같다. #include #include using namespace st..

백준 11403번: 경로 찾기

문제 링크 : https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어 : BFS 한 줄을 탐색하면서, 값이 1인 것인 정점을 기준으로 탐색함. 그래서 답으로 사용할 배열의 값을 1로 변경. #include #include #include #include using namespace std; int N; int nMap[101][101]; int nAns[101][101]; int nChecked[101][101]; queue q; void BFS(int y) { q.push(y); w..

백준 7562번: 나이트의 이동

문제 링크 : https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ... www.acmicpc.net 아이디어 : BFS 현재 위치에서 나이트가 갈 수 있는 곳을 Queue에 넣고 돌린다. 항상 문제는 BFS 돌리더라도..