백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 1707번: 이분 그래프 (Python)

접근 이분 그래프가 무엇인지부터 찾아보고 이해하고 나서 쉽다고 생각했으나 생각보다 시간초과와 오래 싸웠던 것 같다. 이분 그래프란, 쉽게 말하면 모든 점을 빨강과 파랑 두가지 색으로 칠한다고 했을 때, 선으로 이어져 이웃하는 점들이 항상 서로 다른색으로 칠해질 수 있는 그래프를 말한다. 고로 한 점에서 시작하여 주어진 선들을 따라 진행하면서 이전 단계와 다른 색을 칠해주면서 탐색했을 때, 다음 칸이 이미 칠해진 같은 색을 가지고 있다면 이분 그래프가 아닌 것으로 판단해주면 된다. 코드 import sys def bfs(a): q.append(a) visited[a] = 1 while q: now = q.pop(0) for i in range(len(lines[now])): if visited[lines[..

2021. 4. 14. 21:14
코딩/백준 (Python)

백준 7562번: 나이트의 이동 (Python)

접근 미로찾기와 동일하지만 그 이동이 위, 아래, 왼쪽, 오른쪽 4방향이 아니라 사진에 나와있는 것과 같이 나이트가 이동할 수 있는 8방향을 다음 탐색에 추가해주면 된다. BFS를 이용한 미로찾기 참고 링크: 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python) 백준 2178번: 미로 탐색 (Python) 접근 문제 설명과 같이 BFS 알고리즘은 해당 위치까지 최단거리로 이동하는 특성이 있다. 예를 들어 첫 칸인 (0, 0)을 탐색할 때 BFS 알고리즘에 따라 현재칸을 기준으로 위, 아래, 왼쪽, 오른쪽 칸 ca.ramel.be 코드 import sys dx = [2, 2, 1, 1, -1, -1, -2, -2] dy = [1, -1, 2, -2, 2, -..

2021. 4. 13. 00:20
코딩/백준 (Python)

백준 1697번: 숨바꼭질 (Python)

접근 이전에 풀었던 미로탐색 등 BFS의 최단경로 방문 특성을 통해 푸는 문제이다. 조금 다른 점은 기존 문제는 좌표를 기준으로 위, 아래, 왼쪽, 오른쪽을 탐색했다면, 이 문제에서는 순간이동하는 2 * x, x + 1, x - 1을 다음 탐색 범위에 넣어주면 된다. BFS 최단 경로 방문 특성 참고 문제: 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python) 백준 2178번: 미로 탐색 (Python) 접근 문제 설명과 같이 BFS 알고리즘은 해당 위치까지 최단거리로 이동하는 특성이 있다. 예를 들어 첫 칸인 (0, 0)을 탐색할 때 BFS 알고리즘에 따라 현재칸을 기준으로 위, 아래, 왼쪽, 오른쪽 칸 ca.ramel.be 한가지 잊기 쉬운 점은, n ..

2021. 4. 12. 20:51
코딩/백준 (Python)

백준 7569번: 토마토 (Python)

접근 바로 전 토마토 문제와 유사하고, 풀이 방법도 유사하다. 참고하여 풀면 될 것 같다. 다만 기존 코드에 높이 변수만 추가하여 작성했더니 Python에서 시간초과, PyPy3에서 시간안에 풀어주었다. while q: 부분을 bfs 함수로 만들어주었더니 간신히 Python에서도 시간안에 통과하였다. BFS 유사 문제 참조: 2021.04.11 - [코딩/백준 (Python)] - 백준 7576번: 토마토 (Python) 백준 7576번: 토마토 (Python) 접근 문제 자체는 간단한 BFS 문제였으나, 날짜를 입력하는 새로운 리스트를 만들어서 계산했을 때 시간초과가 나와서 조금 헤메게 되었다. BFS 연관문제 : 2021.04.11 - [코딩/백준 (Python)] - 백준 2178 ca.ramel...

2021. 4. 11. 18:41
코딩/백준 (Python)

백준 7576번: 토마토 (Python)

접근 문제 자체는 간단한 BFS 문제였으나, 날짜를 입력하는 새로운 리스트를 만들어서 계산했을 때 시간초과가 나와서 조금 헤메게 되었다. BFS 연관문제 : 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python) 백준 2178번: 미로 탐색 (Python) 접근 문제 설명과 같이 BFS 알고리즘은 해당 위치까지 최단거리로 이동하는 특성이 있다. 예를 들어 첫 칸인 (0, 0)을 탐색할 때 BFS 알고리즘에 따라 현재칸을 기준으로 위, 아래, 왼쪽, 오른쪽 칸 ca.ramel.be 처음에 토마토판을 처음부터 끝까지 탐색하면서 1, 즉 토마토가 있는 칸을 큐에 추가해주었다. 그리고 큐에서 한개씩 popleft 시키면서 해당 칸의 위, 아래, 왼쪽, 오른쪽이 0,..

2021. 4. 11. 18:12
코딩/백준 (Python)

백준 2178번: 미로 탐색 (Python)

접근 문제 설명과 같이 BFS 알고리즘은 해당 위치까지 최단거리로 이동하는 특성이 있다. 예를 들어 첫 칸인 (0, 0)을 탐색할 때 BFS 알고리즘에 따라 현재칸을 기준으로 위, 아래, 왼쪽, 오른쪽 칸을 탐색하게 되는데, 이 칸들에 지금 칸 숫자에 1을 더한 2를 입력해준다. 이 다음 탐색에서는 주변 칸들에 3을 입력하는 식으로 진행하게 되면 마지막 칸에 최단거리를 표시하게 된다. 코드 import sys def bfs(x, y): global cnt dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] q = [[x, y]] visited[x][y] = 1 while q: now = q.pop(0) for i in range(4): nx = now[0] + dx[i] ny = now[..

2021. 4. 11. 17:20
반응형