Algorithm/Graph13 [백준] 16624번 피리 부는 사나이 _ Python https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 1. Preview 풀이 시간: 35분 + 30분 시간 복잡도: O(NM) 공간 복잡도: O(NM) 2. 초기 접근 방법 board[][] 에서 모두 방문하는데 "dfs 탐색를 진행한 횟수" 라고 생각해 풀었다. 3 4 DLLL DDDU RRRU 곰곰히 고민해보니, 위와 같은 case에서 dfs 탐색이 3번 일어나지만, 필요한 safezone은 1개이다. 3. .. 2024. 3. 10. [백준] 11559번 Puyo Puyo _ Python [초기 접근 방법] '애니팡' 같은 느낌의 문제 4개 이상이 인접한 구역이 있는지를 체크해서 폭탄을 터트린다. 이 때 일단 모든 맵에서 bfs()로 인접 지역을 체크하고 터트릴 폭탄이 있는 경우 터트리고 맵을 내려, 다시 인접한 구역이 있는지 확인한다. [생각] 폭탄이 터트리고, 공백의 칸을 어떻게 내리는지 고민했던 문제 1) 일단 '.'으로 초기화하자 2) 그리고 각 플로우마다 맨 아랫줄부터 . 그리고 그 윗줄에 색깔이 있으면 교환하는 형식으로 내려오는 걸 구현하자 for i in range(11, -1, -1): for j in range(6): if board[i][j] != '.': # 아래에 빈 칸이 있는지 확인하고, 있으면 전부 내려버려 for k in range(11, i, -1): if b.. 2024. 2. 1. [백준] 1325번 효율적인 해킹 _ Python https://www.acmicpc.net/problem/1325 [초기 접근 방법] - '한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호' 출력 - 각 노드, 즉 각 컴퓨터에서 bfs 탐색을 하며 그 깊이를 측정하고 가장 깊은 노드를 출력하면 오름차순으로 출력한다. [생각] - 단순한 그래프 탐색 문제 [코드] # 풀이 시간 : 15분 # 시간복잡도 : O(N+e) # 공간복잡도 : O(N+e) # 참고 : - # Python3는 시간초과 from collections import deque def bfs(k): visited = [False] * (N + 1) # 계속 초기화 필요 cnt = 0 # 연결된 간선 갯수 세기 q = deque() q.append(k) visited[k] = Tr.. 2023. 11. 28. [백준] 1600번 말이 되고픈 원숭이 _ Python https://www.acmicpc.net/problem/1600 [초기 접근 방법(x)] 1. 일단 도보로만 이동한다고 생각하고, 목적지까지의 이동횟수를 구한다. (bfs) 2. 목적지에서 K번 '말'의 방향으로 뛰어본다. (dfs) - visited[][] 값이 있을 경우, 즉 도보로 갈 수 있는 경우 result 값을 갱신한다. [생각] 위의 접근이 틀린 이유는, 중간에 '말' 동작을 실행할 수도 있다는 것이다. 저 방법대로라면, 끝에서밖에 '말' 동작을 실행한다. 아예 틀린 접근으로 시간을 소비하고, 블로그를 참조하여 다시 풀이했다. 아.. 그리고 python에서 3차원 배열을 정의하는데, 개념을 잡느라 시간을 많이 썼다. lst = [[[0 for _ in range(depth)] for _ i.. 2023. 11. 27. [백준] 5547번 일루미네이션 _ Python [초기 접근 방법] 1. 정육각형이므로, 6개의 지역에 접근해야 한다. - 짝수 행, 홀수 행에 따라 육각형의 탐색 범위가 달라진다. 2. 그런데 닫힌 구역을 어떻게 판단하지? - 이 부분에 대해서 visited[i][j] == 6 일 경우로 판단하자 라고 생각했지만, 닫힌 구역내의 육각형이 여러 개일 경우 불가한다.. [생각] 예전에 팀프로젝트로 미로찾기 알고리즘을 한 적이 있었는데, 기능 중 하나로 '닫힌 구역에 대해서 미로가 더 이상 탐색하지 않게끔 한다.' 가 떠올랐다. 각설하고, 생각을 해보았지만 닫힌 구역에 대한 판단에 대한 알고리즘이 떠오르지 않아 블로그를 참조했다. 1. 한 번에 바깥쪽의 공간 지역 전체 탐색하기 위해, 상하좌우 4개의 구역을 1칸씩 늘려준다. 2. 주변 6개의 인접 구역.. 2023. 11. 27. [백준] 16918번 봄버맨 _ Python [초기 접근 방법] 1초 - 초기 상태 2초 - 폭탄이 설치되어 있지 않은 모든 칸 폭탄 설치 3초 - '초기 폭탄'의 인접 지역 펑! 4초 - 폭탄이 설치되어 있지 않은 모든 칸 폭탄 설치 5초 - 2초에 설치된 폭탄 펑! 6초 - 폭탄이 설치되어 있지 않은 모든 칸 폭탄 설치 7초 - 4초에 설치된 폭탄 펑! [생각] 홀수∙짝수 시간에 대한 규칙을 찾고, 폭탄을 구분해서 어떻게 터트릴까 고민했던 문제 왜 이렇게 오래 걸렸을까? → 머리로만 생각하지말고, 직접 메모로 기록하면서 반복되는 규칙을 찾자 [코드] # 풀이 시간 : 1시간 30분 # 시간복잡도 : O((N/2) * (5B + RC)) # N회 반복 # 홀수 : bfs 폭탄 터지기 (5개 간선, 폭탄 개수 B) # 짝수 : 모든 칸 폭탄 설치.. 2023. 11. 26. 이전 1 2 3 다음