[Python/파이썬] 백준 2146 - 다리 만들기

문제 설명 입력과 출력 및 예제 풀이 코드 이 문제를 풀기 위해서는 두 단계의 BFS를 사용하여 섬을 구분 짓고, 각 섬까지의 거리를 측정하여 최단 거리를 찾는 방법으로 구현하였다. 첫 번째 BFS(각 섬에 번호를 부여): 섬의 개수를 파악하고 각 섬의 영역을 식별하기 위해, BFS 알고리즘을 사용하여 섬에 고유한 번호를 부여한다. 두 번째 BFS(각 섬에서 다리를 놓아 도달 가능한 다른 섬까지의 거리를 측정): 섬의 땅 덩어리에서 다리를 놓기 시작하여, 다른 섬에 도달할 때까지 다리의 길이를 카운트한다. 이 때, BFS를 사용하여 땅 덩어리에서 시작하여 조건에 맞는 이동을 반복하며, 이동 거리를 업데이트한다. 정답 코드 from collections import deque import sys input..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 6. 12.
• textsms

[Python/파이썬] 백준 2589 - 보물섬

문제 설명 입출력 예제 풀이 코드 처음에 육지중에 땅의 크기가 가장 큰 섬를 bfs로 구한다음에 가장 큰 섬에서 또 bfs로 보물 사이의 최단거리를 구해야하나? 라고 생각했다. 하지만 그럴 필요 없이 두 섬에서 보물 사이의 거리가 가장 먼 값을 구하면 된다. 정답 코드 from collections import deque import sys input = sys.stdin.readline r, c = map(int, input().split()) board = [list(input().rstrip()) for _ in range(r)] dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): q = deque() q.append((x, y)) visited = [[-..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 6. 9.
• textsms

[Python/파이썬] 백준 2636 - 치즈

문제 설명 입력과 출력 및 예제 풀이 코드 나름 정석적인 BFS 문제 풀이 방식으로 풀수 있는 문제였다. 이 문제를 풀기 위한 핵심은 다음과 같다. bfs 탐색으로 치즈를 녹여가면서 녹인 치즈의 개수를 구하고, 모두 녹기 한시간전의 녹인 치즈의 수를 알아야 하기 때문에 list에 저장해놓는다. 녹일수 있는 치즈의 수가 없을 때 까지 while 반복문을 돌며 다음 반복문이 돌기전에 time을 + 1 증가시킨다. 정답 코드 from collections import deque import sys input = sys.stdin.readline r, c = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(r)] ..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 6. 8.
• textsms

[Python/파이썬] 백준 9019 - DSLR

문제 설명 입출력 예제 풀이 코드 A와 B는 모두 0 이상 10000이하의 수라고 했으므로 visited 배열의 수를 10000으로 초기화 해주었다. 그리고 방문하지 않은 수는 bfs 탐색을 시작한다. 여기서 핵심은 일반적인 bfs 문제의 dx, dy 상하좌우 이동 처럼 D, S, L, R 을 활용하는 것이다. 큰 난이도가 있는 문제는 아니라서 아래 코드와 주석을 참고하면 이해될 것이다. 참고로 테스트 케이스 반복문 때문인지 파이썬으로 제출하면 시간초과가 났고 PYPY3로 제출하니 통과할 수 있었다. 정답 코드 from collections import deque import sys input = sys.stdin.readline def applyCommand(n, command): if command ..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 6. 7.
• textsms

[Python/파이썬] 백준 5014 - 스타트링크

문제 설명 풀이 코드 각 층마다 버튼을 몇번씩 눌려 도달했는지 저장하기 위해 visited[] 배열을 선언하였다. 강호의 위치(S)부터 bfs로 탐색을 시작한다. 강호의 위치(S)가 스타트링크(G)에 도착하면 스타트링크까지 도착하는데 눌린 버튼횟수를 반환한다. visited[cur] 정답 코드 from collections import deque import sys input = sys.stdin.readline f, s, g, u, d = map(int, input().split()) # 층수, 강호, 스타트링크, 위, 아래 visited = [-1] * (f + 1) def bfs(start): q = deque() q.append(start) visited[start] = 0 while q: cur..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 6. 6.
• textsms

[Python/파이썬] 백준 1697번 - 숨바꼭질

문제 설명 풀이 코드 숨바꼭질 3번 문제와 완전 똑같은데 순간이동시 시간이 1초 소요된다는 점만 다르다. [Python/파이썬] 백준 13549 - 숨바꼭질3 문제 설명 입출력 예제 풀이 코드 동생의 위치 k에 도달할 때 까지 문제에 주어진 3가지 이동방법으로 탐색한다. 문제에 주어진 범위 0 hstory0208.tistory.com 동생의 위치 k에 도달할 때 까지 문제에 주어진 3가지 이동방법으로 탐색한다. 문제에 주어진 범위 0

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 6. 4.
• textsms