[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

[Python/파이썬] 백준 7562 - 나이트의 이동

문제 설명 입출력 예제 풀이 코드 전형적인 bfs (너비 우선 탐색) 문제 이지만 딱 한가지 다른점이 있다. 바로 이동방향이다. 문제의 이동 방향을 보면 실제 체스의 나이트가 이동할 수 있는 것 처럼 대각선으로 2칸씩 8방향으로 움직인다. 나이트의 이동방향을 표현하면 다음과 같이 표현할 수 있다. 정답 코드 from collections import deque import sys input = sys.stdin.readline dx = [1, 1, 2, 2, -1, -1, -2, -2] dy = [-2, 2, -1, 1, -2, 2, -1, 1] def bfs(x, y): q = deque() q.append((x, y)) while q: x, y = q.popleft() if x == ex and y ..

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

[Python/파이썬] 백준 7569 - 토마토

문제 설명 입출력 예제 풀이 코드 이 문제는 이전의 7576번 토마토 문제와 유사하지만 3차원 배열을 사용한다는 점이 다르다. [Python/파이썬] 백준 7576 - 토마토 문제 설명 입출력 예제 풀이 코드 처음에는 시작지점의 인덱스 값을 bfs(x, y) 이런식으로 넘겨 탐색하도록 했지만 "예제 입력3"번 케이스에서만 계속 전혀 다른값이 나왔다. 이유는 다음과 같았다 hstory0208.tistory.com 3차원 배열을 사용한다는 점과, 6방향(앞,뒤,상,하,좌,우)로 움직인다는 점에 유의하자 정답 코드 from collections import deque import sys input = sys.stdin.readline m, n, h = map(int, input().split()) # 열, 행..

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

[Python/파이썬] 백준 14502 연구소 - (BFS + 백트래킹)

문제 설명 입력과 출력 입출력 예제 풀이 코드 풀이 핵심 벽의 개수가 3개를 설치한 모든 2차원 배열(경우의 수)를 구한다. 3개의 벽이 설치된 2차원 배열마다 bfs()로 탐색하여 가장 큰 안전지대 개수로 갱신한다. 정답 코드 pypy3로 제출하여야 시간초과 없이 통과 from collections import deque import sys import copy input = sys.stdin.readline n, m = map(int, input().split()) # 행, 열 virus_map = [list(map(int, input().split())) for _ in range(n)] result = 0 dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] # 백트래킹으로 3개의 ..

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

[Python/파이썬] 백준 7576 - 토마토

문제 설명 입출력 예제 풀이 코드 처음에는 시작지점의 인덱스 값을 bfs(x, y) 이런식으로 넘겨 탐색하도록 했지만 "예제 입력3"번 케이스에서만 계속 전혀 다른값이 나왔다. 이유는 다음과 같았다. field[x][y]의 값이 1일 때 bfs(x,y)를 시작해 한칸씩 이동하는데, 예제 입력3번 케이스는 시작점이 2개이기 때문에 첫 번째 시작지점 탐색을 시작 할 때 field의 값을 +1씩 추가하고, 또 두번 째 시작지점에서도 bfs(x,y)를 시작해 field의 값을 +1 씩 추가하게 되어서 발생하는 문제였다. 이 부분을 해결하기 위해서는 queue의 특징을 이용해서 걍 시작점마다 한번씩 벌어가면서 탐색하도록 해야하는데 그러기 위해서는 시작점에 해당할 경우 먼저 queue에 시작점을 다 추가해놓고, 그..

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

[Python/파이썬] 백준 1937 - 욕심쟁이 판다

문제 설명 입출력 예제 풀이 코드 어느 지점에서 출발해야 최대한 많은 칸을 지날 수 있는지를 찾아야 하기 때문에 각 지점별로 dfs로 재귀적으로 탐색하며 해당 위치에서 얼만큼 이동할 수 있는가를 dp에 저장한다. 답은 최대한 많은 칸을 이동해야하므로 가장 많은 칸을 이동할 수 있는 칸수를 dp에 저장된 값을 통해 반환한다. 정답 코드 import sys sys.setrecursionlimit(10 ** 8) input = sys.stdin.readline n = int(input()) forest = [list(map(int, input().split())) for _ in range(n)] dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] def dfs(x, y): if dp[x][y..

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