본문 바로가기

Algorithm/DFS&BFS

 (22)
DFS BFS 정리 velog.io/@woo0_hooo/%EB%8F%99%EB%B9%88%EB%B6%81-DFS%EC%99%80-BFS [동빈북] DFS와 BFS 그래프를 탐색하는 대표적인 알고리즘 DFS와 BFS에 대해 알아보았다~ velog.io
[Python] 백준 10026번 : 적록색약 (G5) #문제 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net #풀이 & 학습한 내용 R,G가 구분될때와 R,G가 구분안될때의 2차원 리스트를 따로 만들어줘서 그래프를 탐색하면 되는 문제입니다. 그동안은 전역변수로 인자를 통해 전달하지 않았던 것들이 상황이 2가지가 되어 인자로 상황에 맞는 것을 전달해줘야 했습니다. 이때, python은 mutual type이면 인자로 받은 변수를 직접 변경할 수 있습니다. cf) www.pymoon.com/entry/Pyt..
[Python] 백준 2583번 : 영역 구하기 (S1) #문제 www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net #풀이 & 학습한 내용 단지번호붙이기(supremo7.tistory.com/176)에서 초반에 그래프를 채워주는 것만 추가된 문제입니다. 나눠진 영역의 개수와 나눠진 영역 각각의 넓이를 구해야 합니다. 이는 BFS나 DFS로 그래프를 탐색해서 경로가 있는 vertex들을 살펴볼 수 있습니다. #소스코드 from collections import deque #bfs에서 큐 쓰기위해 im..
[Python] ★ 백준 4963번 : 알파벳 (G4) #문제 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net #풀이 & 학습한 내용 백트래킹의 기본 동작원리를 이해할 수 있는 문제입니다. dfs를 수행하기 전에 방문처리를 하고, dfs를 수행한 후에는 방문처리를 해제해 줘야하는 것이 문제의 핵심입니다. bfs로의 풀이에 대해서도 좀 더 고민해볼 필요가 있습니다. #소스코드 import sys input=sys.stdin.readline #시간초과 방지 dx=[0,0,1,-1] dy=[1,-1,0,0] #..
[Python] 백준 4963번 : 섬의 개수 (S2) #문제 www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #풀이 & 학습한 내용 유기농 배추(supremo7.tistory.com/179)와 같은 문제이나, 다른 점은 대각선으로 있는 것도 연결 된다고 보는 것입니다. 이는 dx,dy에 대각선 4방향만 추가해주면 됩니다. #소스코드 from collections import deque #bfs에서 큐 쓰기위해 dx=[0,0,1,-1, 1,-1,1,-1] dy=[1,-1,0,0, 1,-1,-1,1] #상하좌..
[Python] 백준 14502번 : 연구소 (G5) #문제 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net #풀이 & 학습한 내용 브루트포스로 서로다른 세 좌표를 구하고, 모두 0(빈칸)이면 1(벽)로 바꿔서 벽을 세운 후 dfs/bfs를 수행해야 하는 문제입니다. 이때, 서로다른 세 좌표를 itertools.combination을 이용했는데, 이 부분을 정확히 익힐 필요가 있습니다. #소스코드 import copy,sys,itertools from collections import deque #큐 쓰기위해 input=s..
[Python] 백준 11724번 : 연결 요소의 개수 (S2) #문제 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 #풀이 & 학습한 내용 DFS 또는 BFS로 그래프를 탐색해서 연결된 요소의 개수를 구해야 합니다. 이때, dfs를 쓰려면 재귀깊이를 꼭 늘려줘야 합니다. 유기농 배추(supremo7.tistory.com/179)와 매우 유사한 문제로 풀이가 비슷합니다. #소스코드 from collections import deque #bfs에서 큐 쓰기위해..
[Python] 백준 2573번 : 빙산 (G4) - DFS&BFS 필수문제4 #문제 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net #풀이 & 학습한 내용 2차원 리스트를 실시간으로 갱신시키면서 그래프탐색을 하면 안되고, 다른 2차원 리스트를 선언후 복사붙여넣기해서 초기의 2차원 리스트를 변형시키지 않고 탐색을 진행해야 하는 문제입니다. 이때 반드시 깊은 복사를 해야되고, 이에 대한 설명은 justdoit709.tistory.com/52에 자세히 나와있습니다. #소스코드 from collections import deque #큐..

티스토리툴바