너비 우선 탐색 (6) 썸네일형 리스트형 백준 1707 이분그래프 - 파이썬 문제. 풀이. 이분 그래프는 연결된 정점마다 색을 칠한다고 하면 연결된 정점 끼리의 색이 서로 달라야한다. 즉 예를 들어 (1,3), (2,3) 이 연결되어 있다면 1은 빨간색 3은 파랑색 2는 빨간색 이런식으로 연결된 정점끼리의 색이 달라야한다. 풀이. from collections import deque def bfs(n): visited[n] = 1; queue=deque() queue.append(n) while queue: x = queue.popleft() for i in matrix[x]: if visited[i] == 0: visited[i] = -visited[x] queue.append(i) else: if visited[i] == visited[x]: return False retur.. 백준 7562 나이트의 이동 - 파이썬 문제. 풀이. BFS를 해서 문제를 풀면된다. 나이트의 이동 범위만 잘 정해서 하면되는데 Y축으로 2칸 올라갈때는 X축이 -1, +1 만큼 움직이고 Y축으로 1칸 올라갈떄는 X축이 -2, +2 만큼 움직인다 소스코드. import sys from collections import deque def BFS(matrix, start, end): if start == end: return 1 queue = deque() queue.append([start[0], start[1]]) while queue: x, y = queue.popleft() for i in range(8): nx = x + dx[i] ny = y + dy[i] if 0 백준 1697 숨바꼭질 - 파이썬 문제. 풀이. 처음에는 그냥 굉장히 쉬울거라 생각하고 풀었는데 런타임 에러도 나고, 44퍼센트에서 틀렸다고 뜨기도해서 뭐가 문제인지 찾는데 시간이 좀 걸렸다. 우선 기본적인 BFS 방식으로 풀면되는데 주의 해야할 점은 찾아야 K가 N보다 작을 수 있다는 점을 간과하고 리스트를 K크기만큼 선언을 하였어서 실패했었고, 크기를 K, N 값중 더 큰 값으로 배열을 선언했다가 44퍼센트에서 틀렸었다. 생각해보니 찾아야할 점이 100000이여도 배열을 100000만큼만 선언하여서는 안된다 x2를 했다가 돌아오는 경우가 있기 때문에 배열 범위를 넉넉하게 잡아줘야한다. 소스코드. import sys from collections import deque def BFS(n): queue = deque() queue.app.. 백준 7569 토마토 - 파이썬 문제. 풀이. 7576 토마토 문제와 3차원 배열인 점만 다르고 똑같다. 3차원 배열의 인덱스가 어떻게 이루어져 있는지 잘 생각하고 BFS에 적용을 하고 입력받은 3차원 배열에서 1의 위치를 큐에 넣고, BFS를 실행한 후 배열에 0이 있으면 -1을 출력하고 0이 없다면 배열의 최댓값에서 -1을 출력을 한다. 소스코드. import sys from collections import deque def BFS(): while queue: z, x, y = queue.popleft() for i in range(6): nx = x+dx[i] ny = y+dy[i] nz = z+dz[i] if (0 백준 7576 토마토 - 파이썬 문제. 풀이. 우선 1의 위치를 큐에 넣어주고 BFS를 실행한다. BFS 실행 후 리스트에 0이 남아있다면 -1을 출력하고 그렇지 않다면 리스트의 최댓값에서 -1을 출력한다. deque를 사용하지 않고 리스트를 사용해서 제출하면 시간초과가 난다. 소스코드. import sys from collections import deque def BFS(): while queue: x, y = queue.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] if (0 백준 1012 유기농 배추 - 파이썬 문제. 풀이. BFS를 이용하여 1을 만나면 BFS를 실행하고 방문한곳은 0을 처리해준다 한번 BFS가 끝나면 배추흰지렁이의 갯수를 +1 해준다. 소스코드. import sys def BFS(y, x): queue = [[y, x]] while queue: a, b = queue[0][0], queue[0][1] del queue[0] for i in range(4): ny = a+dx[i] nx = b+dy[i] if 0 이전 1 다음
