웹개발 성장기

1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net DP문제이고 두 가지 방식으로 풀 수 있다. Top-Down 풀이 DFS 재귀를 이용한다. 목적지인 arr[N - 1][N - 1]에 도달했을 경우 1을 return한다. 처음 방문하는 위치일 경우에만 DFS를 수행한다. 정답일 경우 1이 계속 return하면서 올 것이므로 cnt[x][y] += solve(nx, ny); 을 해준다. 그렇지 않으면 기존 값 (cnt[x][y])을 return한다. 방문체크는 처음에 cnt배열을 -1로 초기화한 후 방..

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 처음에 사이클 체크를 어떻게 해야 하는지 엄청 고민했다... 결국 구글링하여 솔루션들을 참고했다 ㅠ 내가 시도하려는 풀이에선 방문체크 배열이 두 개가 필요함을 알 수 있었다. 방문 체크를 할 배열, 완전히 방문이 끝났음을 알리는 배열 두 개의 visited를 확인할 배열이 필요 visited[n] = false: 아직 방문안한 곳이므로 DFS 다음 탐색 node는 n visited[n] = true & finished[n] = false 방문은 했으나 완전히 방..

DFS 백트래킹 문제에 cctv를 설치하는 부분만 신경써주면 쉬운 문제 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 CCTV의 5가지 종류에 대해 조합으로 방향 정보를 구성하고 DFS를 짜주면 끝나는 간단한 문제이다. 방향 정보를 어떻게 나타낼지 고민을 많이 했다.. 우선 처음에 사무실 정보를 입력받을 때 카메라 번호 및 위치, 그리고 해당 카메라의 방향 정보 개수 (d)를 ArrayList에 넣는다. 방향 정보 개수는 아래 그림과 같다. 방문체크는 visited 2차원 배열을 만들어 해당 ..