[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/파이썬] 백준 16953 - A -> B

문제 설명 입출력 예제 풀이 코드 이 문제는 딱 보고 BFS 문제다라고 생각하진 못했지만 너비 우선 탐색 알고리즘 카테고리를 풀고 있기 때문에 BFS로 문제를 풀어 보았다. 큐에 연산을 통해 값이 변할 a와 첫 연산 횟수 1을 튜플로 묶어 추가해준다. 큐가 빌 때 까지 a의 뒤에 숫자 1을 추가한 수와 a * 2를 한 수를 추가하여 연산 횟수를 하나씩 올린다. 만약 a의 수가 b보다 크면 다음 큐를 꺼내어 확인한다. a와 b가 같다면 연산횟수 cnt를 출력하고 종료한다. 큐가 빌때 까지 a와 b가 같지 않다면 -1을 출력한다. 아래의 사진은 a : 2 , b : 162 일 때 bfs를 통해 나온 (a, cnt) 값들이다. 처음에는 a > b 일 때 continue를 하지 않아 정답과 다른 값이 나왔는데 ..

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

[Python/파이썬] 백준 13460 - 구슬 탈출2

문제 설명 입출력 예제 풀이 코드 골드1 난이도인 만큼 이전 BFS문제보다 상당히 까다로웠다. 1. 먼저 빨강 공과 파란 공의 위치를 방문했는지 확인할 필요가 있다. 이 부분을 visited 리스트에 공들의 위치 값을 튜플로 넣어 방문 여부를 확인하였다. 2. 주어진 입력 값에서 빨강 공의 위치와 파란 공의 위치를 반환. getPos()라는 메서드를 만들어 각 공의 위치를 반환하도록 하였다. 3. 각 공이 구멍전까지 도달하는데 걸리는 기울이기 횟수를 구한다. move() 함수를 통해 이동하는 위치가 벽이아니고, 구멍에 들어가지 않을 동안 반복하여 각 공의 기울이기 횟수를 구하였다. 이 기울이기 횟수는 두 공의 위치가 겹쳤을 경우를 처리하기 위해 사용한다. 4. bfs를 통해 빨강 공이 구멍에 도달하면 r..

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

[Python/파이썬] 백준 16234 - 인구 이동

문제 설명 입출력 예제 풀이 코드 더 이상 인구 이동이 일어나지 않을 동안 bfs 탐색을 통해 연합을 이루는 나라들을 구한다. 연합을 이루는 나라가 2개 이상이라면 연합인구수의 평균을 구해 인구이동을 시작한다. 인구 이동이 없다면 반복문을 종료하고 인구 이동이 발생한 횟수를 출력한다. 정답 코드 from collections import deque import sys input = sys.stdin.readline n, l, r = map(int, input().split()) country = [list(map(int, input().split())) for _ in range(n)] dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] cnt = 0 def bfs(x, y): q = d..

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

[Python/파이썬] 백준 13549 - 숨바꼭질3

문제 설명 입출력 예제 풀이 코드 동생의 위치 k에 도달할 때 까지 문제에 주어진 3가지 이동방법으로 탐색한다. 문제에 주어진 범위 0

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

[Python/파이썬] 백준 16236 - 아기 상어

문제 설명 입출력 예제 풀이 코드 먼저 bfs()에서 탐색을 시작할 아기 상어의 자표를 먼저 구해야한다. 그렇게 하지 않고 while문 안에서 아기 상어의 좌표를 찾을 경우 n^3으로 시간초과가 발생한다. 핵심은 다음과 같다. bfs()에서 먹을 수 있는 물고기들을 반환하는데, 가장 거리가 가까운 물고리를 우선적으로 먹으므로 이를 거리순, x좌표순, y좌표순으로 반환한다. 그리고 while문을 통해 더이상 먹을 물고기가 없을 때 까지 반복문을 실행한다. 정답 코드 from collections import deque import sys input = sys.stdin.readline n = int(input()) sea = [list(map(int, input().split())) for _ in ran..

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