'BFS' 태그의 글 목록

본문 바로가기

BFS

백준 10026 | 적록색약 [파이썬] https://www.acmicpc.net/problem/10026 풀이문제 보고 두 가지 해결방안이 떠올랐다.첫 번째는 주어진 입력으로 적록색약이 아닌 사람이 봤을 때 구역 수를 먼저 구한 뒤에 그리드 내의 R 또는 G를 한 가지 색으로 통일시켜 적록색약인 사람의 구역 수를 구하는 방법두 번째는 BFS로 돌리면서 현재 색이 R 또는 G 일 때, 상하좌우도 R 또는 G 면 큐에 넣어 구역 수를 구하는 방법어쨌든 둘 다 적어도 그래프 탐색을 두 번 호출해야 해결할 수 있다. 코드import sys, copyfrom collections import dequesys.setrecursionlimit(10000)input = sys.stdin.readlineN = int(input())grid = [list(.. 더보기

백준 2206 | 벽 부수고 이동하기 [파이썬] https://www.acmicpc.net/problem/2206 풀이 처음에 14502번 - 연구소 문제처럼 맵(그래프)을 하나하나 돌면서 벽이 있다면 그 벽을 부수고 bfs 돌려보고 최단거리가 아니면 다시 그 자리에 벽을 세우고 다른 벽을 부수어보는 방식으로 해결하려고 코드를 짰는데, 시간 초과 가 나왔고 두 번째 시도에는 틀렸습니다 가 나왔다. 그래서 다른 방법으로 시도해야겠다는 생각으로 다른 분들의 풀이 방법을 보았고 또, 2206번 문제 FAQ 글이 있길래 봤는데... 일단 이 해결 방식은 정답이 될 수 없다. 이유는 2가지가 있었는데, 첫 번째는 시간 복잡도가 너무 크게 나오는 것이다. 연구소 문제 같은 경우에는 N, M 범위가 작아서 하나하나 방문해도 시간 복잡도가 크지 않았지만 이 문제는 .. 더보기

이전 1 다음

티스토리툴바