https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 1. Logic 방에 들어갈 때 .이나 $이면 들어갈 수 있기 때문에 방 주변을 이동 가능한 공간으로 둘러싸서 입구를 찾아준다. BFS함수 안에서 각 열쇠마다 키가 없을 때 방문했던 좌표를 queue에 저장해놓고 키를 찾으면 queue에서 뽑았던 좌표를 빼서 확인해준다. 아이디어가 신박했다. 2. Code #include using namespace std; int dx[4] = {-1, 0, 1, 0}; i..
알고리즘
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. Logic 대표적인 백트래킹 문제. 문제를 푸는 로직은 아래와 같다. 1. 입력을 받으면서 0의 갯수(채워야 하는 빈칸의 갯수)를 같이 카운트한다. 2. solve함수의 파라미터로 0을 넣고 스도쿠 칸이 총 81칸이기 때문에 나누기, 나머지 연산자로 y, x칸의 좌표를 구한다. 나눗셈 연산 : y, 나머지 연산 x 3. 가로, 세로, 3*3에 이미 나온 숫자들이 있는지 확인하고 1~9까지 돌..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1. Logic 처음에 문제를 봤을 때 유니온 파인드로 푸는 줄 알았다. 정 안풀려서 블로그를 참고해서 풀이했다,, r1-r2, rn-r1 끼리 팀을 맺는다는 말은 순환이 있는 그래프끼리 팀을 맺는다는 말이다. 재귀를 활용해서 vis배열에 방문을 처리하면서 방문처리된 배열에 group배열(그룹이 만들어졌다는, 순환하는 그래프의 노드를 표시)이 false라면 그룹을 만들 수 있는 상황이기 때문에 연결된 ..
https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 1. Logic 기본 DFS문제. 간단하게 T를 피해서 DFS 돌려주고 이동 거리가 맞는것만 count해주면 된다. 2. Code #include using namespace std; int r, c, k; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; char graph[6][6]; bool vis[6][6..
https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 1. Logic 처음에 DP로 될거같아서 시도했는데 DP는 vis배열을 찍고 나오기 때문에 최단거리 계산이 안된다. 그리고 vis배열을 기록을 안하게 되면 루프를 계속 들어가기 때문에 힙이 터진다..ㅋㅋㅋㅋ 결국 BFS 느낌으로 해결 이 문제에서 " 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다."는 배수만큼 앞으로 이동 + 배수만큼 뒤로 이동할 수 있다. 2...
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 1. Logic 여기서 주의해야 할 점은 바이러스가 퍼지면서 비활성 바이러스에 닿게 되면 그 부분은 시간으로 처리를 안해준다. 문제에 따로 명시는 되어있지 않지만 테스트 케이스를 설명해주는 그림을 잘 보면 그렇게 되어있다... 1. 문제를 푸는 로직은 먼저 입력받으면서 바이러스가 있는 좌표를 저장해놓는다. 2. 바이러스를 활성화 할 수 있는 갯수가 정해져있기 때문에 조합을 활용해서 m개만큼 활성화 할 바..
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. Logic 시작점에서 시작하여 모든 노드를 순회하면서 연결된 모든 노드까지의 최단거리를 갱신한다. 한 노드에서 모든 노드까지의 최단거리를 구하는 문제이기 때문에 다익스트라 알고리즘을 사용했다. 2. Code #include using namespace std; const int INF = 0x3f3f3f3f; int n..
https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 1. Logic 이 문제를 풀 때는 산봉우리의 의미를 잘 파악하는 것이 중요하다. 문제에서 정의한 산봉우리는 " 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.)" 라고 했다 인접은 X, Y좌표가 1이하로 차이나야 하기 때문에 (1,1)을 중심으로..
https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 1. Logic BFS로 노드를 지날 때 마다 거리를 더해주며 BFS를 돌면 된다. 입력을 받을 때 양방향으로 받아주고 m개를 입력 받을 때 마다 vis배열만 초기화 잘 시켜주면 된다. 2. Code #include using namespace std; int n, m; vector graph[1001]; bool vis[1001]; int BFS(int start, int e..
https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 www.acmicpc.net 1. Logic 입력을 받은것을 기반으로 숫자 입력을 받을 때 마다 vis배열에 체크를 하고 for문을 돌며 각 빙고 라인들을 체크해준다. 2. Code #include using namespace std; int bingo[5][5]; int vis[5][5]; int check1() { int ret = 0; for(int i = 0; i < 5; i++) if(vis[i][0] && vis[i][1] &&..
