본문 바로가기

Algorithm/DFS&BFS

 (22)
[Python] 백준 2468번 : 안전 영역 (S1) - DFS&BFS 필수문제3 #문제 www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net #풀이 & 학습한 내용 DFS 또는 BFS로 구분되는 영역의 최대 갯수를 구하는 문제입니다. #소스코드 from collections import deque #큐 사용하기 위해 dx=[0,0,1,-1] dy=[1,-1,0,0] #상하좌우 def bfs(q): #bfs로 경로있는 vertex들 모두 방문처리 while q: v=q.popleft() now_x=v[0] now_y=v[1] #큐에서 뽑은 vertex..
[Python] 백준 5014번 : 스타트링크 (G5) - DFS&BFS 필수문제2 #문제 www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net #풀이 & 학습한 내용 현재 층수에서 목표 층수까지 이동하는 최소 횟수를 구하는 문제입니다. 가중치가 없으므로 최단경로를 bfs를 통해 구해줍니다. #소스코드 from collections import deque def bfs(q): while q: v=q.popleft() now_floor=v[0] #큐에서 뽑은 현재 층 now_count=v[1] #현재 층까지의 이동횟수 if now_floor==find_floo..
[Python] 백준 2644번 : 촌수계산 (S2) - DFS&BFS 필수문제1 #문제 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net #풀이 & 학습한 내용 인접리스트로 그래프를 저장한 뒤에, 출발점에서 도착점까지의 최단경로를 계산하는 문제입니다. 가중치 없는 간선을 가진 최단경로는 bfs를 이용하면 됩니다. #소스코드 from collections import deque #큐 사용하기 위해 def bfs(q): while q: v=q.popleft() now_v=v[0] #현재의 vertex count=v[1] #현재의..
[Python] 백준 1707번 : 이분 그래프 (G4) - DFS&BFS단계별11 #문제 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net #풀이 & 학습한 내용 "그래프 순회를 통해 이분 그래프를 판별하는 문제"입니다. 이분 그래프를 판정하는 방법으로 인접한 vertex가 서로 다른 두 가지 색으로만 그래프가 칠해진다는 점을 이용하면 됩니다. 이때, 그래프가 연결 그래프라는 조건이 없으므로, disconnected graph에 대해서도 고려하며 문제를 풀어야 합니다. input()을 쓰면 PyPy3에서는 통과되지만 Python..
[Python] 백준 7562번 : 나이트의 이동 (S2) - DFS&BFS단계별10 #문제 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net #풀이 & 학습한 내용 "나이트를 목적지까지 이동시키는 최소이동횟수"를 구하는 문제입니다. bfs로 최소경로를 구하면 답을 구할 수 있으며, visited 리스트를 따로 선언해주어 이미 방문한 곳은 큐에 넣지 않도록 구성해야 시간초과에 걸리지 않습니다. #소스코드 from collections import deque #큐 사용하기 위해 dx=[2,2,-2,-2,1,1,-1,-1] dy=[1,-1,1,-1,..
[Python] 백준 2206번 : 벽 부수고 이동하기 (G4) - DFS&BFS단계별9 #문제 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net #풀이 & 학습한 내용 "현재 상태"를 정점으로 표현하여 그래프를 만들고 최단거리를 구하는 문제입니다. bfs로 최단거리를 구하는 미로찾기 문제에서, 벽을 하나 부술 수 있다는 옵션이 추가되었습니다. 이때 방문여부를 판단하는 visited를 벽을 부순 케이스와 벽을 안 부순 케이스로 나누어 따로 관리해주어야 하는 것이 이 문제의 핵심입니다. velog.io/@jengyoung/b..
[Python] 백준 1697번 : 숨바꼭질 (S1) - DFS&BFS단계별8 #문제 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #풀이 & 학습한 내용 "또 다른 BFS 최단거리 연습문제"입니다. BFS를 통해 가장 최소횟수를 구해주며, 현재위치의 범위와 방문여부로 중복을 제거해야 메모리초과에 걸리지 않고 문제를 해결할 수 있습니다. #소스코드 from collections import deque #큐 사용하기 위해 def bfs(q): while q: #K위치에 도달할 때까지 계속 반복(도달불가능한 경..
[Python] 백준 7569번 : 토마토 (S1) - DFS&BFS단계별7 #문제 www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net #풀이 & 학습한 내용 supremo7.tistory.com/207?category=874979의 3차원 버전 문제입니다. 여기서 정말 주의해야 될 점은 Z방향으로 리스트를 참조할 때 tomatoes[위아래][가로][세로]로 Z값이 맨 앞에 온다는 점입니다. 이 부분을 잘 생각하면서 코드를 짜야 합니다. #소스코드 from collections import deque #큐 사용하기..

티스토리툴바