백준 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,..
백준 7576 토마토 BFS (파이썬)
2022. 9. 10. 17:02
백준
아이디어 시작점이 여러개인 bfs탐색을 활용해야겠다. (독가스가 퍼지는 상황과 비슷하다.) visited에 시작점으로 부터의 거리를 넣어놓자. 풀이 import sys from collections import deque def bfs(N, M): # 여러개의 시작점을 갖는 bfs, 시작점에서의 거리를 탐색하며 알아냄 for i in range(N): for j in range(M): if tomato[i][j] == 1: Q.append((i, j)) while Q: i, j = Q.popleft() for di, dj in [[0, 1], [1, 0], [-1, 0], [0, -1]]: nr, nc = i + di, j + dj if 0
백준 1012 유기농 배추 DFS (파이썬)
2022. 9. 5. 19:54
백준
아이디어 이거 전에 풀어봤던 단지번호붙이기랑 똑같다. 그거 보다 쉽다. 영역의 갯수만 알아내면 되기 때문. 2667_단지번호붙이기 dfs사용하자. 풀이 및 해설(주석) import sys sys.setrecursionlimit(10 ** 6) # 일단 혹시 몰라 넣어줌 def dfs(N, M, r, c): # 미로에서 dfs를 사용하는 것과 같이 재귀 dfs를 선언 visited[r][c] = 1 for dr, dc in [[0, 1], [1, 0], [0, -1], [-1, 0]]: nr, nc = r + dr, c + dc if 0