C30 [C] 1697: 숨바꼭질 사실 이 문제가 BFS 관련 문제라는 것을 빨리 깨달았다면 구현은 생각보다 쉽게 할 수 있었을 것이다. 그냥 어떻게 풀지 모르겠어서 각 경우의 수를 나누어 구해보고 있었는데 5에서 시작해 17로 가기 위한 경우를 그리던 중 가지가 뻗어지는 tree형태인 것을 확인할 수 있었다. 그리고 몇 초만에 갔는지 확인해야하므로 BFS 관련 문제인 것을 파악했다. 모르겠으면 무식하게 좀 해봐야겠다. 특히 이 문제 같은 경우는 갈 수 있는 방법이 3가지이므로 가지가 3개인 tree인 것을 알 수 있다. 그리고 2차원 배열을 구현할 때 각 index를 써주는 것이 귀찮아서 그냥 처음에 int *ret0=&queue[front][0];로 선언하였더니 코드가 더 깔끔하고 읽기 쉽게 느껴졌다. 또 queue[1000000][.. 2023. 8. 23. [C] 1074: Z 맨 처음 생각했던건 이차원 배열 graph[40000][40000]을 잡고 돌아다니면서 수를 저장하여 r행 c열을 몇번째로 방문했는지를 확인하는 거였다. 하지만 이렇게 할 경우 512MB라는 메모리 제한에 걸리게 된다. 따라서 DecideSquare이라는 함수를 만들어서 r행 c열까지 재귀적으로 가는 동안 4가지 사각형 중 어디로 가야할지를 정하게 된다면 탐색에 걸리는 시간 뿐만 아니라 메모리도 아끼게 된다. 여기서 주의해야할점은 재귀 함수를 쓸때 각 조건을 잘 살펴야하고 언제 return을 해야하는지를 잘 생각해야한다. 그리고 pow()를 쓸때는 double형 변수를 써야한다! #include #include void recursion(double n,int x,int y,int x_target,int.. 2023. 8. 23. [C] 11403: 경로 찾기 문제는 정점 (i,j)에 대해서 i에서 j로 가는 길이가 양수인 경로가 있는지 확인하는 프로그램을 짜야한다. 여기서 알아야할 알고리즘은 Floyd's Algorthim으로 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우' 사용이 가능한 알고리즘이다. 2차원 배열에 저장을 하며 노드의 개수가 N개라고 할 때 N번만큼의 단계를 반복하여 리스트를 갱신하기 때문에 DP라고 볼 수도 있다. 이 알고리즘의 점화식은 Dab=min(Dab,Dak+Dkb)이지만 이 문제를 풀 때는 최단 경로가 아닌 경로가 있는지 확인만 하면 되기 때문에 코드가 조금 다를 수 있다. 그리고 이 점화식의 시간복잡도는 O(n^3)이다. #include #include int graph[101][101]; int mai.. 2023. 8. 23. [C] 21736: 헌내기는 친구가 필요해 간단하게 풀 수 있는 문제였다. X가 벽이고 O로 지나갈 수 있으며 P를 만날때 people++을 해주면 된다. 그리고 결국 그래프를 순회만 하면 되기 때문에 Depth-first를 이용해 풀어주었다 #include #include char graph[601][601]; int visit[601][601]; int people=0; int x_coordinate[4]={0,0,1,-1}; int y_coordinate[4]={1,-1,0,0}; void dfs(int x,int y,int x_max,int y_max) { for(int i=0;i 2023. 8. 23. 이전 1 2 3 4 5 6 7 8 다음