bfs

문제 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 정답 소스코드 (Python) def dfs(vert,start): visited[vert]=True value=field[vert] if not visited[value]:dfs(value,start) elif visited[value] and value==start:result.append(value) n=int(input()) field=[0] result=[] for i in range(n):field.append(int(input())..

문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 정답 소스코드 (Python) from collections import deque count,dx,dy=0,[0,0,1,-1],[1,-1,0,0] def bfs(): queue=deque() queue.append([0,0]) cost[0][0]=field[0][0] while queue: x,y=queue.popleft() for i in range(4): nx,ny=x+dx[i],y+dy[i] if -1

문제 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 정답 소스코드 (Python) from collections import deque n,k=map(int,input().split()) limit=100001 cnt=[0]*limit visited=[False]*limit def bfs(x,end): queue=deque() queue.append(x) while queue: x=queue.popleft() if x==end:return cnt[x] if -110 (+1..

문제 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 정답 소스코드 (Python) from collections import deque n,m=map(int,input().split()) field=[] visited=[[False for j in range(m)]for i in range(n)] arr=[[-1 for j in range(m)]for i in range(n)] for i in range(n): tmp=list(map(int,input().split..

문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 (Python) from collections import deque n=int(input()) arr=[] result=[] #각 단지의 집의 수 count=0 #result에 입력하기 위한 count변수 for _ in range(n):arr.append(list(map(int,list(input())))) visited=[[False for i in range(n)] for j in range(n)] #방문 여부 확인 def bfs(x,y): qu..