백준/DFS&BFS

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 문제에 대한 자세한 내용은 백준에서 참고해주세요 풀이 1. 택시 운전자는 가장 가까운 거리에 있는 고객을 먼저 태워야 합니다. (만일 같은 거리에 존재하는 고객이 여러 명이라면 최소 행 위치에 있는 고객을 태우며, 같은 행에 존재하는 고객이 여러 명이라면 최소 열 위치에 있는 고객을 태운다) 이 때 정렬이 필요함을 알 수 있습니다. 2. 택시 운전자의 ..

https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 문제 풀이 1. BFS알고리즘을 사용해서 문제를 풀어주기로 했습니다. 2. 우선 완전탐색을 통해서 백신을 놓기 전의 격자와 백신을 놓은 후의 격자를 비교해줍니다. 3. 만일 다른 데이터 값을 가진 격자 위치를 찾게 되면 그 격자 위치를 중심으로 백신을 놓기 전의 격자 위에 백신을 놓은 후의 격자의 데이터 값으로 수정하는 BFS탐색을 진행해줍니다. 4. 만..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 풀이 한칸 당 독립적인 국가라고 생각하면 됩니다. 이동 가능한 경로를 dxys 튜플을 통해 정의하고, 너비 우선 탐색(BFS)를 통해서 연합이 될 수 있는 국가인지 확인하기로 했습니다. 여기서 연합이 될 수 있는 조건은 두 국가의 인구 차이가 L 이상 R 이하이면 조건을 만족합니다. visited 배열을 boolean으로 관리하여, 해당 국가를 방문했는지 여부를 체크합니다. 인..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 BFS알고리즘을 적용해서 주어진 S초가 지난 뒤에 갱신된 grid에서 목표 값을 출력해준다. 코드 # 18405번 경쟁적 전염 import sys from collections import deque n, k = map(int, sys.stdin.readline().split()) grid = [] queue = [] for i in range(n): li = ..

https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 BFS 알고리즘을 사용해서 문제를 풀어주었습니다. 3차원 리스트이기에 주의해서 짜주시면 됩니다. 코드 # 6593번 상범 빌딩 import sys from collections import deque dxyzs = ((0,0,1), (0,0,-1), (1,0,0), (-1,0,0), (0,1,0), (0,-1,0)) while True: L, R, C = map(int, sys.stdin.read..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 BFS알고리즘을 사용하였습니다. 코드 # 2573번 빙산 import sys from collections import deque dxys = [[1,0],[-1,0],[0,1],[0,-1]] # bfs 두번 실행 def bfs(s_x, s_y): queue = deque([]) queue.append([s_x, s_y]) visited[s_y][s_x] = True while queu..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 BFS 문제 풀이를 위해서 기존에 자료구조를 deque으로 사용하였지만 이번에는 set으로 구현해주었습니다. 더군다나 지나온 경로를 일일이 set이나 list에 저장할 경우 메모리 초과가 발생하기에 문자열로 저장해주었습니다. 다음번에는 경로문제가 생길경우에 DFS를 우선시해서 풀어보겠습니다. 코드(BFS) # 1987번 알파벳 dxys = [[1,0],[-1,0],[0,1],[0,-1..