BFS

3055 백준 파이썬

정말 쉽지 않았던 문제 뭔가 새로운 방법을 얻은 것 같다. 새로 리스트를 만들어서 재귀시켰더니 메모리 초과가 났다. 그래서 q의 길이를 줄이면서 q를 진행시켰다. from collections import deque dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def bfs(x, y): q.append([x, y]) c[x][y] = 1 while q: qlen = len(q) while qlen: x, y = q.popleft() for i in range(4): X = x + dx[i] Y = y + dy[i] if 0

2665 백준 파이썬

미로 찾기 + A같은 느낌... 처음에는 dfs를 통해 계속 고르는 개수를 증가시키면서 해결하려고 했으나 결국은 검은 방도 모두 탐색해야하므로, 흰방을 모두 탐색한 뒤에, 검은방 탐색시키면 됐었던 문제. 그래서 흰방은 append를 해줬고, 검은 방은 appendleft를 해주었다. 결국은 bfs의 bfs. 였다. 탐색에 대한 생각을 다시한번 하게 해줬던 문제. #https://www.acmicpc.net/problem/2665 from collections import deque def bfs(x,y): dx=[-1,1,0,0] dy=[0,0,-1,1] q=deque() q.append((x,y)) while q: x,y=q.popleft() for i in range(4): X=x+dx[i] Y=y+..

1967 백준 파이썬

이 문제를 풀려면 어떤 임의의 점에서 가장 많이 떨어진 점은 지름의 한 점에 해당한다는 점을 알고 있어야 한다. 그림을 통해 보면 원 내부의 직선에서 어떤 점을 잡든, 그 점에서 가장 먼 점은 원의 지름의 한 끝에 해당하는 점이 된다. 그리고, 그 점에서 가장 먼 점을 찾아 연결하면 그것이 바로 원의 지름에 해당한다. 따라서 이런 트리가 있다고 가정해 보자. 이 노랑색 루트 노드에서 가장 먼 점은 빨강색 노드이다. 그리고 빨강 노드에서 가장 멀리 떨어진 점을 찾는다. 이게 바로 파란색 점이다. bfs를 통해 해결했다. 다익스트라를 통해 해결해도 문제 없을 것 같다. from collections import deque n=int(input()) tree=[[] for _ in range(n+1)] for..

2638 백준 파이썬

딱봐도 BFS 냄새가 진하게 나는 문제. 차이점은 외부공기와 내부공기의 구별이다. 힌트는 모눈종이 바깥쪽에는 치즈가 없다는 점이다. 코드 구성 0. (0,0)에서 bfs를 진행시켜 진행된 좌표를 vis에 표기한다. 1. vis와 기존 좌표배열(l)의 합이 0이라면, 내부공기에 해당하므로, 2로 변환해준다. 2. 치즈를 찾는다. 3. 치즈 좌표 중 위아래오른쪽왼쪽을 비교하여 1개 이상의 방향에서 외부공기(0)가 찾아지면 제거한다. 4. 내부공기에 해당하는 좌표를 0으로 바꾸어 준다. 5. 이하 t번 반복하여 합이 0이될때까지 계속한다. 코드 from collections import deque import sys sys.setrecursionlimit(10**5) input=sys.stdin.readlin..

2206 백준 파이썬

오랜만의 bfs, dfs 항상 그렇듯, dfs는 시간초과다. 처음 짠 코드 from collections import deque import sys input=sys.stdin.readline n,m=map(int,input().split()) M=[] for _ in range(n): M.append(list(str(input()))) def bfs(x,y,Mcopy): vismap=[[0 for x in range(m)] for y in range(n)] q=deque() cnt=1 q.append([x,y,cnt]) while q: x,y,cnt=q.popleft() a=[-1,1,0,0] b=[0,0,-1,1] for t in range(4): X=x+a[t] Y=y+b[t] if 0

BFS, DFS 스페샬 (백준 1012, 2178, 1389, 1697)

이전 게시글에서 BFS와 DFS에 대해 다뤘었다. 이번에는 그 응용. 첫번째는 1012번이다. 말이 어렵지 그냥 1 연속된 칸의 갯수를 구하는 문제다. (x,y)의 값만 잘 설정한 뒤에는 dfs든 bfs든 상관없이 풀이해도 된다. t=int(input()) for _ in range(t): stack=[] li=[] cnt=0 x1=[1,-1,0,0] x2=[0,0,1,-1] m,n,k=map(int, input().split()) space=[[0]*n for x in range(m)] check=[[0]*n for x in range(m)] for _ in range(k): a,b=map(int, input().split()) space[a][b]=1 li.append([a,b]) for x in r..

탐색 알고리즘 -dfs와 bfs (백준 1260)

그들과의 첫 조우 - 백준 1260번 이번 문제, 푸는데 20시간은 걸린거 같다. 그만큼 몰랐던 개념이 많았던 문제고 그에따라 많은 개념을 익혔다. 일단 문제를 풀며 가장 난이도를 느낀 부분이 그래프의 구현이었다. 나는 애초에 그래프가 뭔지도 몰랐다. 그리고 스택과 큐 역시 전공수업을 들으며 대충은 개념을 알고 있었지만, 실제로 써본 것은 처음이었다. 1. 그래프 그래프란 정점과 간선으로 이뤄진 자료구조다. 정확하게는 정점사이의 관계를 나타낸 자료다. 자 이걸 어떻게 프로그램한테 설명할 것인가? 크게 두가지 방법으로 표현 할 수 있다. 1) 인접 행렬 정점의 수에 따라 n*n의 2차원 리스트를 생성한뒤, 그 내용을 0으로 채워넣는다. 그 후에 1,2라는 정점사이에 간선이 존재한다면 arr[1][2]=1,..