SWEA 5176 이진탐색 (파이썬)
2022. 9. 13. 19:49
SWEA
https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 아이디어 처음엔 어떻게 접근해야 할지 조차 몰랐다. 답은 1부터N까지의 숫자들을 이진탐색트리로 만들면 매우 쉽게 나온다. 근데 숫자들을 보면 1, 2, 3, 4, 5, 6이 들어가 있는 위치가 중위순회를 했을 때 나오는 값이다. 위의 이진탐색트리를 중위순회하면 1, 2, 3 ,4, 5, 6이 나온다. 이걸 이용한다. 이를 트리의 값으로 저장하면 된다. 풀이 및 해설 cnt = 1 def make_tree(v): global cnt if v ..
SWEA 5174 subtree (파이썬)
2022. 9. 13. 19:44
SWEA
https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 아이디어 간단하다. 트리의 간선 정보가 있고, 이를 이용해서 트리의 왼쪽, 오른쪽 자식을 넣어주고 전위든 중위든 후위든 탐색하여 1씩 더하면 된다. 풀이 cnt = 0 def inorder(v): global cnt if v == 0: return inorder(L[v]) cnt += 1 inorder(R[v]) return cnt for tc in range(int(input())): E, N = map(int, input().split(..
백준 2206 벽 부수고 이동하기 (파이썬)
2022. 9. 12. 19:10
백준
풀이 import sys; from collections import deque def bfs2(): Q.append((0, 0, 0)) visited[0][0][0] = 1 while Q: r, c, z = Q.popleft() if r == N-1 and c == M-1: # 도착지점에 도달하면 return return visited[r][c][z] for di, dj in [[1, 0], [0, 1], [0, -1], [-1, 0]]: nr, nc = r + di, c + dj if 0
백준 2660 회장뽑기 BFS (파이썬)
2022. 9. 12. 16:51
백준
아이디어 bfs탐색을 통해 친구의 친구의 친구.... 를 시작점 부터의 거리로 두면 될 것 같다. 근데 정확히 점수가 어떻게 반영되는지는 모르겠다. 일단 bfs 탐색 해보자. 풀이 import sys; from collections import deque, defaultdict def bfs(v): visited = [-1] * (N + 1) # bfs함수 내에서 visited를 초기화 visited[v] = 0 # 시작점은 0으로 초기화 Q.append(v) while Q: v = Q.popleft() for w in G[v]: if visited[w] == -1: visited[w] = visited[v] + 1 Q.append(w) return max(visited) # visited의 최대값이 점..
백준 2636 치즈 BFS (파이썬)
2022. 9. 11. 19:18
백준
아이디어 bfs를 사용해서 치즈를 녹여야 될 것 같다. 시간과 마지막 남아 있는 치즈는 일단 코드를 짜보면서 생각하자. 풀이 import sys; from collections import deque ''' 이 문제의 핵심은 bfs를 통해 치즈를 녹이는 것이다. 외부인 공기에서 bfs를 시작하여 치즈를 녹이는 것이다. ''' def bfs(N, M): Q.append((0, 0)) visited = [[0] * M for _ in range(N)] visited[0][0] = 1 total = 0 while Q: r, c = Q.popleft() for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]: nr, nc = r + di, c + dj if 0
백준 2589 보물섬 BFS (파이썬)
2022. 9. 11. 17:31
백준
아이디어 문제가 정확히 뭘 요구하는지 애매하다. 시작점에서 가장 멀리 있는 거리를 구하라는 것 같은데 일단 bfs로 구현해보자. 풀이 import sys; from collections import deque def bfs(N, M, r, c): Q.append((r, c)) visited = [[0] * M for _ in range(N)] # 이 문제의 경우, visited를 bfs 함수 안에 넣어줘야한다. visited[r][c] = 1 sums = 0 while Q: r, c = Q.popleft() for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]: nr, nc = r + di, c + dj if 0
백준 2468 안전 영역 DFS (파이썬)
2022. 9. 11. 15:43
백준
아이디어 탐색 할 때 추가적으로 높이를 인자로 넣어줘야한다. 높이는 1부터 101까지 이다. for문을 통해 높이를 전달하자. 풀이 import sys sys.setrecursionlimit(10 ** 6) def dfs(N, h, r, c): visited[r][c] = 1 for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]: nr, nc = r + di, c + dj if 0 = k and visited[i][j] == 0: # 높이 k이상인 지역을 탐색 dfs(N, k, i, j) tmp += 1 if tmp > result: result = tmp print(result) 후기 이 문제는 비에 잠긴 구역이 아닌, 잠기지 않은 구역을 찾아야 했다. 처음에는 잠긴 ..
백준 7569 토마토 3차원 BFS (파이썬)
2022. 9. 10. 20:12
백준
아이디어 전에 풀었던 7576 토마토 문제의 연장이다. 토마토를 받을 배열과 visited를 3차원으로 변경하고 BFS를 돌려보자 풀이 import sys; from collections import deque def bfs(H, N, M): for h in range(H): for i in range(N): for j in range(M): if tomato[h][i][j] == 1: Q.append((h, i, j)) visited[h][i][j] = 1 while Q: h, i, j = Q.popleft() ''' 3차원 리스트에서의 움직임의 델타를 추가하면 된다. 2차원의 델타가 [1, 0].. 이었다면, 3차원은 [1, 0, 0], [0, 0, 1]... 등으로 주면 된다. ''' for dh,..