본문 바로가기

알고리즘 & PS69

[BOJ] 벽 부수고 이동하기 4 (16946, G2) 벽을 하나 부쉈을 때 그 자리에서 연결된 칸 수는 몇 칸인지 구하는 것이다.생각보다 판이 좀 커질 수 있어서, 그냥 하나하나 다 구하기엔 당연히 TLE 걸릴 것이라 다른 방법이 필요하다.그러면 벽 바로 상/하/좌/우 1칸을 기준으로 빈 연결된 공간의 개수를 더해주면 된다!  하면 틀린다. 빈 공간이 연결되어 있을 수 있다. 뭔 소리냐1111110011101011101111111붉은 1을 잘 보면, 1을 부수면 6칸이 되어야 한다. 하지만 1에 연결되어 있는 상/하/좌/우 만 더하면3 + 3 + 1 + 1 = 8칸으로 맞지 않는다. 무엇이 문제일까?- 연결된 영역을 중복해서 세서는 안된다.- 자기 자신도 포함해야 한다.이 두 가지 문제를 어떻게 해결해야 할까?BFS로 영역을 세는 문제는 많이 풀어보았을 것.. 2024. 11. 20.
[BOJ] 가장 오래 걸리는 스도쿠 (G3, 12095) https://www.acmicpc.net/problem/12095 이 문제는 역으로 코드 해석이 필요한 문제이다.해당 코드는 백트래킹으로 풀고 있다. 1부터 차례대로 넣으면서 아니면 거르고 거르고...그렇다면, 맨 앞칸부터 9 8 7 6... 이렇게 오게 만들면 가장 마지막까지 탐색해야 하므로, 이를 강제화 시키면 된다.정확히는 맨 첫 칸에서 삽질하게 만들면 된다. 그리고 그 다음칸도 삽질하게 만들고 만들고...(너무 그러다가 답안이 중복답안이 나오면 망할 수 있으니 욕심내진 말고..)그리고, 이걸 직접 1부터 넣어서 해보게 실패 시키면 깔끔하게 만점. 이렇게 되는 스도쿠 아무거나 하나 던져주면 된다.더, 백트래킹을 어렵게 할 수도 있지만, 이정도만 해도 만점이 너무  충분하다.        3    .. 2024. 11. 19.
[BOJ] 치킨 배달 (G5, 15686) - 잃어버린 3시간 https://www.acmicpc.net/problem/15686 다 해놓고 얼탱이 없는 미스로 3시간을 날렸다. dfs 돌릴 때 돌아갈 다음 칸을 잘못 설정하였다... 얼탱이 없는 오타...dfs(pick_num + 1, i + 1) 해야 한다는걸 dfs(pick_num+1, cur_pos+1) 해버림....그 외에는 G5치고는 쉬운 그냥 dfs.잃어버린 나의 3시간....import sysinput = sys.stdin.readlinedef chick_dist(chick_list, house_list): global min_length sum_dist = 0 for cur_h in house_list: cur_min_dist = sys.maxsize for .. 2024. 11. 18.
[BOJ] 감시 (G3, 15683) https://www.acmicpc.net/problem/15683 골드 3 다운 쉽지  않은 문제.처음 들었던 생각은 이거 어차피, 각 카메라가 비출 수 있는 최대 칸을 그리디하게 비추면 되는거 아닌가?하지만, 몇 가지 문제가 있다.(1) 동률일 경우 어떻게 처리?(2) 동률일 경우 방향을 겹치게 비춰주면 그리디하다고 꼭 최대는 아님.. 안겹치게 비춰줘야 최대... 아 복잡..즉, 그리디로는 풀기 어려우니 DFS 해 줘야 한다.각 카메라별로 회전 방향이 정해져있는데, 두 개 이상의 경우는 두 개 이상의 방향이 합쳐졌다고 고려하면 된다.1번 카메라는 상/하/좌/우2번 카메라는 상하/좌우3번 카메라는 상좌/상우/하좌/하우4번 카메라는 상하좌/상하우/상좌우/하좌우5번 카메라는 상하좌우이 각각 중 1개씩 고르.. 2024. 11. 16.
[BOJ] 웜홀 (G3, 1865) - 벨만-포드 알고리즘 튜토리얼 https://www.acmicpc.net/problem/1865그 동안 학습한 최단 경로 구하기 알고리즘은 다음과 같다.- 다익스트라 알고리즘 : 힙 기반, 간선이 모두 양의 가중치일 때만 사용 가능 - 플로이드-워셜 알고리즘 : DP기반, 모든 거리를 구해주지만 V^3 만큼의 시간복잡도....이 문제는 일단 웜홀의 존재 이유 때문에 다익스트라는 사용 불가능하다.게다가 이 문제는 여러 번 워프를 타면서 시간을 돌릴 수 있는지?를 물어본다.플로이드-워셜 알고리즘에서 음의 가중치를 갖는 루프를 찾기 위해서는 자기 자신으로 돌아오는 지점의 , 즉 dp[i][i] 문제는 시간 복잡도 때문에 터져서 불가. 이 문제는 벨만-포드 알고리즘을 사용해야만 한다. 벨만-포드 알고리즘의 핵심은 모든 edge를 항상 활용한.. 2024. 11. 16.
[BOJ] 플로이드 (G4, 11404) : 플로이드-워셜 vs 다익스트라 https://www.acmicpc.net/problem/11404  이 문제를 다익스트라, 플로이드-워셜 둘 다 써서 풀어보았습니다. (1) 다익스트라- 하나의 시작점에서 각 점들까지의 최단 경로를 계산합니다.- heap 기반 알고리즘으로 최단 비용을 차례 차례 뽑아나가는 방식입니다.- 그리디 알고리즘 기반이며, 음수 가중치가 포함될 경우 다른 방법을 써야 합니다.- 시간 복잡도 : ElogV# solution (1) dijkstra로 풀어 보기. 하나의 점에서 거리 구하기.# Time complexity: VlogE# 특징점 : 음의 가치에서는 사용 불가!import sysimport heapqinput = sys.stdin.readlineINF = 1e12vertex = int(input())edg.. 2024. 11. 15.

티스토리툴바