문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 어떻게 풀 것인가? BFS에서 중복 방문에 대한 체크를 삭제 해야 접근이 가능했던 문제였다. 중복 방문을 허용하게 된다면, 여러가지의 경우수 접근 자체가 불가능하다. 최단 시간을 구하라는 점은 숨박꼭질1번 문제와 똑같지만, 이번에는 최단 시간에 만나는 모든 경우를 구해야 한다. 즉, 생각해보자. 1. 방문 탐색을 하면서 시간을 계산해야한다. 2. 또한 경..
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 어떻게 풀 것인가? 문제를 최단경로라는 키워드를 발견 다익스트라 알고리즘이라고 생각했다. 다만 해당 N명의 인원들이 X라는 목적지 파티까지 가는 경로의 최단경로와 그리고 X에서 N명의 인원들이 집까지 가는 최단경로를 구한이후 그 중에 가장큰 거리를 출력해야한다. 풀면서 놓쳤던점 다익스트라에 대한 이해가 부족해서 아래와 같은 블로그를 참고하였다. 나중에 시간이 된..
문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 어떻게 풀 것인가? 처음에는 DP를 생각했다. 하지만 문제를 계속해서 틀렸고, 생각의 흐름을 바꿨다. 그래프를 이용한 BFS 문제였다. 다만 인접행렬이 아닌 일차원 배열 형태의 입접리스트로 풀어야했다. BFS를 이용 visit과 timezone이라는 배열을 생성이후에 100,000이라는 범위에서 시간과 방문형태를 계속 계산한다. 그리고 큐가 전부 비워지면..
문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제에 대한 이해 벽을 최대 1개까지 부술수 있으며, 0,0 ~ N-1, M-1까지 가야하는 탐색 문제이다. 어떻게 풀 것인가? 최근에 공부했던 0-1BFS를 응용하여 문제를 접근했다. 다만 응용기법이 잘 못되었는지 계속 틀려서 어쩔수 없이 아랫분의 블로그를 참고했다. https://iseunghan.tistory.com/316 백준 2206번 : 벽 부수고 이동하기..
문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제에 대한 이해 그래프에 관련된 문제이다. 다만 아래에 설명에도 기재하겠지만, 일반적인 그래프문제는 아니였다. (내 기준에서는 그랬다.) 어떻게 풀 것인가? 처음에는 BFS로 접근했으나 벽을 어떻게 부술지에 대한 생각이 많았고, 몇 번 문제를 틀리다보니 문제에 대한 접근이 잘못되었다는 것을 알았다. 그래서 문제에 대하여 검색을 해보았는데..... 0-1 BFS라는 방식..
문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제에 대한 이해 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 리프 노드의 갯수를 찾는 문제이다. 어떻게 풀 것인가? 주어진 트리에서 그래프 탐색을 이용하여, 리프노드의 갯수를 찾아야한다...
문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제에 대한 이해 문제가 길다고 당황하지 말고 결국에는 DP문제이다. 어떻게 풀 것인가? 위와같이 문제에서 DP라는 생각이 들어서 DP접근을 하여 문제를 풀었다. 타일이 1개일 경우 만들어지는 경우의 수는 1개 타일이 2개일 경우 만들어지는 경우의 수는 2개 타일이 3개일 경우 만들어지는 경우의 수는 3개였다. 타일이 4개일 경우 만들어지는 경우의 수는 5개였다. 위 와같은 방식으로 점화식은 d(..
문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 문제에 대한 이해 그래프 이론에서 DFS를 이용한 풀이를 이용해보면 된다. 이 문제의 경우 영역과 관련된 문제에서 DFS를 이용한 문제들과 많은 연관이 있었다. 그래서 어렵게 풀지는 않았다. 어떻게 풀 것인가? DFS에서 많이 쓰이는 패턴을 쓰면 된다. 이는 코드를 보면 알게된다. W의 영역을 찾아서 제곱하여 값에 더하고 B의 영역을 찾아서 제곱하여 값에 더하고를 모..
