1. 문제 https://www.acmicpc.net/problem/1937 2. 풀이 모든 좌표에서 DFS를 실행하면 $O(N^2)$ x $O(N^2)$ -> $O(N^4)$ 으로 시간 초과가 발생 DFS + DP를 이용하여 시간 복잡도를 줄일 수 있다. dp[i][j] = r map의 (i, j)에서 출발했을 때 최대 이동할 수 있는 칸의 개수 = r 판다가 어디에서 처음 풀어놔야 하는지도 정해야 하기 때문에 모든 좌표에서 DFS 함수를 출발시켜야 한다.($O(N^2)$) DFS 함수에서는 다음과 같은 로직을 수행한다. 출발하는 것도 움직인 것으로 보기 때문에 DFS 함수를 실행하면 dp[x][y] = 1을 통하여 움직임을 더해준다. 4방 탐색으로 좌표를 찾고 현재 내 위치의 대나무의 양보다 다음 위..
1. 문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 2. 풀이 BFS + 비트마스킹으로 해결하는 문제. 좌표 평면에서 BFS 혹은 DFS의 이동을 생각할 때, 흔히 방문한 곳을 다시 방문하지 않기 위해 boolean OR Int형으로 2차원 방문 처리 배열을 만들어 처리한다. 그러나 이 경우는 조건을 가지지 않고 이동하는 경우에는 편리하나, 조건을 가지고 이동하는 경우에는 따로 조건 처리를 해주거나 그리디한..
1. 문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 풀이 외판원(TSP)의 기본 문제 중 하나이다. 노드의 개수 $O(x^n)$ 주요 자료구조 1. int[][] inMatrix : 인접 행렬 2. boolean[] nodeVisited : 노드 방문 처리 배열 입력으로 주어지는 값으로 인접 행렬을 구성한다. 이 문제의 포인트는 최소 값을 가지는 경로는 하나이기 때문에 모든 정점에서 DF..
1. 문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 2. 풀이 백준 2638 치즈 문제와 거의 똑같은 문제(https://www.acmicpc.net/problem/2638) 이 문제의 핵심 또한 가장 자리에는 치즈가 무조건 없으므로, 치즈가 없는 공간(공기 공간)이 외부 공기인지 내부 공기인지 파악하는 것이 중요하다. 주요 변수 및 자료구조 1. Queue pointQueue : 녹을 치즈의 좌표를 저장할 Queue 2. int cnt : while문을 ..
1. 문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 2. 풀이 단순 DFS로 문제 해결 시 시간초과 발생 풀이 Point는 DFS + DP로 DP를 이용하여 다음에 탐색하려는 위치의 DP 값이 지금 현재 Depth보다 크다면 그 부분으로는 탐색을 하지 않는 것이다. 그리고 동전을 무한번 움직일 수 있다는 것은 사이클이 발생할 수 있다는 것이므로 4방 탐색을 체크하면서 방문했던 지점을 또 방문할 수 있다면 이는 사이클이 발생할 수 있다는 ..
1. 문제 2. 풀이 DFS를 이용하여 해결 각각의 배열 요소는 2가지 값을 가진다. 배열에서의 자신의 위치 (=인덱스) 방향 이를 이용하여 인접리스트를 구성할 수 있다. 방향에 따른 노드 번호 연결 방법 ↑ : 자신의 인덱스 - M ↓ : 자신의 인덱스 + M → : 자신의 인덱스 + 1 ← : 자신의 인덱스 - 1 주요 자료구조 boolean[] visited : DFS 방문 배열 boolean[] isCycled : 처리 완료 배열 List[] inList : 인접리스트 int result : 사이클이 생긴 횟수 노드를 연결했다면 0 ~ N - 1번 노드까지 처리 배열이 false라면 pipeDFS() 함수를 시작한다. pipeDFS()는 크게 다음과 같은 4가지 부분으로 나눌 수 있다. 지금 탐색..
1. 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2. 풀이 백준 골드 3에 해당하는 문제로 DFS로 해결했다. 입력을 받고 map을 구성하고 치즈의 개수를 세어 cheeseCnt에 저장한다. 주요 자료구조 int cheeseCnt : 치즈 수 boolean[][] visited : 외부 공기와 내부 공기를 구별할 boolean 배열 Queue pointQueue : 치즈를 녹일 좌표가 들어있는 큐 이 문제의 핵심 포인트는..
1. 문제 https://swexpertacademy.com/main/identity/anonymous/loginPage.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 풀이 Point 링크와스타트 (백준 15661)과 굉장히 유사한 문제이다. 주요 입력 자료구조 peopleCityMap : 도시 별로 인구수가 저장된 Map List[] linkList : 도시 별로 연결되어 있는지를 저장한 연결리스트 boolean[] visited : 도시를 2개의 구역으로 나누기 위한 배열 N개의 구역이 있을 때, A, B 구역으로 나누는 부분 visited 배열의 BackTracking을 통해 True : A ..
