파이썬 알고리즘/DFS, BFS 활용

15.토마토(BFS 활용)

문제 - 생략 문제풀이 import sys from collections import deque sys.stdin=open("input.txt", "r") dx=[-1, 0, 1, 0] dy=[0, 1, 0, -1] n, m=map(int, input().split()) board=[list(map(int, input().split())) for _ in range(m)] dis = [[0]*n for _ in range(m)] Q=deque() for i in range(m): for j in range(n): if board[i][j] == 1: #행단위로 검색하면서 익은 토마토 발견 Q.append((i, j)) while Q: tmp=Q.popleft() for k in range(4): #ran..

14. 안전영역(BFS) vs 안전영역(DFS)

안전영역(BFS) import sys from collections import deque sys.stdin=open("input.txt", "r") dx=[-1, 0, 1, 0] dy=[0, 1, 0, -1] n=int(input()) board=[list(map(int, input().split())) for _ in range(n)] cnt=0 #안전영역의 갯수 res=0 Q=deque() for h in range(0, 100): ch=[[0]*n for _ in range(n)] cnt=0 #높이 h가 바뀌는 경우 cnt를 초기화한다. for i in range(n): for j in range(n): if ch[i][j]==0 and board[i][j]> h: #행단위로 검색하면서 최초로 안..

13.섬나라 아일랜드(BFS 활용)

문제 - 생략 문제풀이 import sys from collections import deque sys.stdin=open("input.txt", "r") dx=[-1, -1, 0, 1, 1, 1, 0, -1] dy=[0, 1, 1, 1, 0, -1, -1, -1] n=int(input()) board=[list(map(int, input().split())) for _ in range(n)] cnt=0 Q=deque() for i in range(n): for j in range(n): if board[i][j]==1: #행단위로 검색하면서 최초로 단지 발견 board[i][j]=0 #부모였을때 이미 방문한 경우 흔적을 남긴다. Q.append((i, j)) while Q: tmp=Q.popleft()..

12.단지 번호 붙이기(DFS)

문제 - 생략 문제풀이 import sys sys.stdin=open("input.txt", "r") dx=[-1, 0, 1, 0] dy=[0, 1, 0, -1] def DFS(x, y): global cnt cnt+=1 #집좌표가 넘어 오면 카운팅 board[x][y]=0 #이미 방문한 경우 흔적을 남긴다. for i in range(4): #range의 범위만큼 자식이 생긴다 xx=x+dx[i] yy=y+dy[i] if 0