백준/DFS&BFS

https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 풀이 BFS를 토대로 문제를 풀어주었습니다. 주난이가 움직이지않고 제자리에서 파동을 보내서 초코바를 훔쳐간 범인을 찾기에 파동의 움직임을 구현해주시면 됩니다. 항상 파동이 전달 될 수 있는 "0"부터 방문할 수 있게 .appendlef()를 사용하여서 학생이 없는 자리인 "1"과 학생이 있는 자리인 1과 구분하여 방문 할 수 있게 코딩해주시면 됩니다. 코드 # 14497번 주난의 난(難..

https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 풀이 sorted(reverse=True)를 이용하여 내림차순을 구현한 뒤 BFS알고리즘을 구현해주시면 됩니다. 코드 # 24445번 알고리즘 수업 from collections import deque import sys # 정점의 개수: N 간선의 수: M 시작정점: R N, M, R = map(int, sys.stdin...

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net BFS 알고리즘으로 문제를 풀어주었습니다. 코드 # 1926번 그림 from collections import deque import sys dxs = [0, 0, 1, -1] dys = [1, -1, 0, 0] grid = [] n, m = map(int, input().split()) for _ in range(n): grid.append(list(map(int, sys.stdin.readline(..

https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 풀이 평범한 BFS문제이며 딕셔너리를 통해서 출력을 해주었습니다. 시간초과 방지를 위해서 sys.stdin.readline()으로 입력을 받아주세요 # 24444번 알고리즘 수업 - 너비 우선 탐색 1 import sys from collections import deque n, m, r = map(int, input()...

https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 # 3184번 양 # r 행 c 열 .빈 필드 # 울타리 o 양 v 늑대 from collections import deque r, c = map(int, input().split()) grid = [ list(input()) for _ in range(r)] visited = [[False]*c for _ in range(r)] dxs = [0, 0, 1, -1] dys = [..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 bfs를 이용해서 갈 수 있는 모든 칸을 방문 처리해준 뒤 bfs 함수가 한 사이클 돌은 횟수가 곧 섬의 개수가 됩니다. # 4963번 섬의 개수 import sys from collections import deque dxys = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]] # bfs 함수 def bfs(x, y): queue =..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이(BFS 풀이) 기존의 BFS문제와 같이 BFS로 주어진 동굴을 탐색할 것입니다. 파이썬에서는 BFS를 사용할 경우 deque를 이용해줍니다.이 deque에 다음 좌표를 집어넣는 조건을 다음과 같이 설정하였습니다. 기존의 저장된 루피 값보다 현재의 루피 값이 작을 경우에만 deque에 좌표를 넣어주었습니다. 모든 좌표가 최소 루피 값을 가질 경우에 BFS함수가 종료됩니다. #..

https://www.acmicpc.net/problem/16469 16469번: 소년 점프 첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다. (2 ≤ R, C ≤ 100) 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다. 숫자 0은 이동 가능한 www.acmicpc.net 풀이 스윙스, 넉살, 창모가 모이는데 최소 경과 시간과 그러한 지점들의 개수를 출력해주는 것이 목표입니다. # 16469번 소년 점프 import sys from collections import deque input = sys.stdin.readline # 좌표 dxs = [0, 0, 1, -1] dys = [1, -1, 0, 0] # row 행, col 열 row, col ..