본문 바로가기

Programming/DFSBFS

Programming/DFSBFS 2022. 4. 29. Programmers / 단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr Solution from collections import deque def solution(begin, target, words): answer = 0 q = deque() q.append([begin,0]) visit = [False]*len(words) while q: word, n = q.popleft() if ..
Programming/DFSBFS 2022. 4. 29. Programmers / 단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr Solution from collections import deque def solution(begin, target, words): answer = 0 q = deque() q.append([begin,0]) visit = [False]*len(words) while q: word, n = q.popleft() if ..
Programming/DFSBFS 2022. 3. 25. Baekjoon / BFS / 음식물피하기 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net Solution from collections import deque import sys input = sys.stdin.readline n,m,k = map(int, input().split()) graph = [[0]*m for _ in range(n)] for _ in range(k): r,c = map(int, input().split()) grap..
Programming/DFSBFS 2022. 2. 13. Baekjoon / BFS / 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net Solution. 1 from collections import deque import sys input = sys.stdin.readline # 시간 초과 해결 n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): x,y = map(in..
Programming/DFSBFS 2022. 2. 13. Baekjoon / DFS / 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net DFS로 문제를 풀이해보았다. Solution. 1 t = int(input()) dx = [0,0,-1,1] dy = [-1,1,0,0] def dfs(board,x,y): if board[x][y] != 1: return if board[x][y] == 1: board[x][y] = 2 for n in range(4): nx = x + dx[n] ny = y + dy[n] if 0>nx or nx>=len..
Programming/DFSBFS 2022. 2. 11. Baekjoon / BFS / 미로탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 너비경로탐색 BFS로 문제를 해결해보았다. from collections import deque n, m = map(int, input().split()) board = [] for _ in range(n): board.append(list(map(int, input()))) dx = [0,0,-1,1] dy = [-1,1,0,0] def bfs(): start = [0,0] queue = deque() queue.append(..
Programming/DFSBFS 2022. 1. 22. Programmers / BFS / 네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr Solution. 1 from collections import deque def solution(n, computers): visited = [[0] * n for _ in range(n)] def bfs(): count = 0 answer = [] for i in range(n): for j in range(n): if computers[i][j] ==..

티스토리툴바