본문 바로가기
반응형

BFS4

[파이썬🐍] 백준 4963 : 섬의 개수 이 문제는 특별하게 대각선까지 확인해준다. 간단히 상하좌우에서 4좌표만 더 찍어주면 된다! import sys sys.setrecursionlimit(100000) dx = [-1, 1, 0, 0, -1, -1, 1, 1] dy = [0, 0, -1, 1, 1, -1, 1, -1] def dfs(x, y, matrix): matrix[x][y] = 0 for i in range(8): nx = x + dx[i] ny = y + dy[i] if (0 2021. 4. 12.
[파이썬🐍] 백준 11724 : 연결 요소의 개수 from sys import stdin n,m = map(int,stdin.readline().split()) matrix = [[0]*(n+1) for _ in range(n+1)] for i in range(m): a,b = map(int,stdin.readline().split()) matrix[a].append(b) matrix[b].append(a) visited = [0]*(n+1) def bfs(v): queue = [v] while queue: v = queue.pop(0) for i in matrix[v]: if visited[i] == 0: queue.append(i) visited[i] = 1 answer = 0 for i in range(1,n+1): if visited[i] == .. 2021. 4. 8.
[파이썬🐍] 백준 2667 : 단지 번호 붙이기 변수가 많아져서 약간 복잡했다. bfs 방식으로 해결할 수 있었다. from collections import deque from sys import stdin def bfs(x,y): dx = [1,-1,0,0] dy = [0,0,1,-1] cnt = 0 queue = deque() queue.append((x,y)) maps[x][y] = '0' visited.append((x,y)) while queue: now=queue.popleft() cnt += 1 for i in range(4): nx = now[0] + dx[i] ny = now[1] + dy[i] if (0 2021. 4. 7.
[파이썬🐍] 백준 2178 : 미로 탐색 stdin.readline()을 사용하는 것이 아직 익숙하지 않다. 정확한 정의를 찾아보다가 알게된 것 -> stdin은 standard input의 약자 readline() : 한 줄씩 읽을 때 사용 rstrip() : 오른쪽 공백이나 문자열 제거 from sys import stdin n, m = map(int, stdin.readline().split()) matrix = [stdin.readline().rstrip() for _ in range(n)] visited = [[0]*m for _ in range(n)] dx,dy = [-1,1,0,0],[0,0,-1,1] queue = [(0,0)] visited[0][0] = 1 while queue: x,y=queue.pop(0) if x == n.. 2021. 4. 7.
반응형

티스토리툴바