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

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 이문제는 BFS를 이용해 l * l 맵 에서 처음가보는 장소가 있다면 직전거리(graph)에다 + 1을해가며 (visited)방문처리를 해주었다. 마지막으로 graph[e_y][e_x]를 해주면 목표지점의 거리가 나올것이다. from collections import deque import sys input = sys.stdin.readline dx = [2, 2, -2, -2, 1, -1, 1, ..

• format_list_bulleted Algorithm
• · 2023. 2. 20.
• textsms

[백준 / 파이썬] 2573 빙산

BFS 함수를 2개만들었다. 1. 1년마다 녹는걸 구현하는 BFS 2. 그 후에 몇덩이로 나눠졌는지 확인하는 BFS를 구현했다. 까다로웠던 부분은 첫번째 BFS에서 바다인 부분은 방문처리를 하면 안된다는 부분이다. 왜냐면 빙산은 상하좌우 빙하의 개수에 의해 깎여나가는데 바다를 방문처리해서 들리지 않게 된다면 깎이는 부분이 적어지기 때문이다. from collections import deque n, m = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] time = 0 def bfs(a, b): global time visited =..

• format_list_bulleted Algorithm
• · 2023. 2. 5.
• textsms

[백준] Python 2667 단지번호붙이기 DFS/BFS

모든 행, 열을 완전탐색하여 1인곳을 찾아 DFS 혹은 BFS로 들어가면된다. BFS 좀 해메었지만 원리는 단순하다. 방문처리가 필요없이 방문한 곳들을 0으로 만들어 주고 cnt를 늘리는 방식으로 단지가 몇개인지 세면된다. from collections import deque n = int(input()) graph = [list(map(int, input())) for _ in range(n)] # 모든 인덱스를 확인하여 1이 있으면 bfs로 지난부분 0으로 만들기., 다 파고들면 다시 방문안한 1부터 dfs house = [] dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] def bfs(r, c): q = deque() q.append((r, c)) graph[r][c] = 0 ..

• format_list_bulleted Algorithm
• · 2023. 2. 4.
• textsms

[백준] Python 2606 바이러스 BFS/DFS로 풀이.

먼저 DFS 풀이. 방문한 노드면 재귀 종료. 방문 안한 노드면 방문처리 해주고 연결된 노드들 확인. from collections import defaultdict n = int(input()) connect_len = int(input()) dic = defaultdict(list) for i in range(connect_len): a, b = map(int, input().split()) dic[a].append(b) dic[b].append(a) # 양방향 # dfs 접근 visited = [False for _ in range(n+1)] # 1번부터 시작하기 위해 n+1 def dfs(v, visited): global cnt if visited[v]: return visited[v] = Tr..

• format_list_bulleted Algorithm
• · 2023. 2. 4.
• textsms