판교의 메타몽

링크 : www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 조건이 각각의 숫자들이 '붙어서' 입력받는 관계로, 먼저 문자형으로 값을 입력 받고 int형으로 바꾸는 과정이 필요되었다. 아스키 코드를 활용한 형변환을 활용했는데, 자세한 사항은 2667번 단지번호붙이기의 초입부를 참고해보자. 문제풀이는 다음과 같다. (1) 값을 입력받을 때, 문자열로 입력받고 해당 값의 -48, 즉, int형으로 변환하여 배열에 저장한다. (2) 맨 처음과 맨 끝도 이동 범위에 포함이 되므로, ch배열의 [1][..

링크 : www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 문제풀이는 다음과 같다. (1) 최초의 시작점을 입력받고, 해당 시작지점을 큐에 넣어준다. (2) 큐에 맨 앞 값을 temp라 지정한다. 그리고 큐의 값을 한 번 pop해준다. 이제부터 temp는 현재 위치를, pos는 +1, -1, *2를 하는 것에 따라 달라지는 위치값이라고 생각해야한다. (3) temp 값의 -1, +1, *2의 값을 순차적으로 for문으로 구해준 ..

링크 : www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 문제의 풀이는 다음과 같다. (1) 배열을 2개 만든다. 하나는 값을 입력받을 값(arr), 다른 하나는 방문 여부를 파악하고 동시에 토마토가 익을 날짜를 누적할 배열(check)이다. (2) 배열에 값을 넣는다. 이때 check(방문여부를 파악하는 배열)는 모두 -1로 채워넣는다. (3) 배열에 입력된 값이 '1'일 경우(즉, 익은 토마토이다), 해당 배열의 쌍을 큐에 넣어주고 ch..

백 트래킹 (Back Tracking) 말 그대로 왔던 길을 다시 추적하는 알고리즘. 즉, 모든 경우를 전부 고려하는 알고리즘이다. 여기까지만 본다면 모든 경우를 하나하나 실험해보는 'Brute Force'가 떠오를 것이다. Brute Force와는 차별화된 Back Tracking의 특징은 필요없는 값은 정답 후보군을 제거해주는 가지치기(Pruning 혹은 Branch and bound)이다. 이 가지치기를 통해 한번 갔던 루트 중, 재방문이 필요없는 루트는 탐색하지 않는다. 백 트레킹에는 크게 3가지 종류가 있다. 스택 혹은 재귀함수를 이용하는DFS(깊이우선탐색, Depth First Search), 큐를 이용하는 BFS(너비우선탐색, Breadth First Search) BFS/HS(최선우선탐색,..