해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 1261번 알고스팟 - BFS

www.acmicpc.net/problem/1261

문제 풀이

1261번 알고스팟 문제는 BFS로 풀수 있는 문제입니다. 

deque를 사용하여 queue에 (map의 y좌표, map의 x좌표, 벽을 뚫고간 개수) 세트로 하여 넣습니다. 

(0,0)부터 넣기 시작하고, 4방향을 검사하여 탐색을 합니다.

벽이 없는 좌표에 가중치를 주어 먼저 들어가도록 appendleft() 함수를 사용하면, 4방향 중 벽이 없는 곳부터 계속 탐색해 나가게 됩니다. 벽이 있는 좌표는 append() 함수를 사용하도록 합니다. 

목적지에 도달할 때마다 값을 비교하여 최소 값을 저장하도록 합니다. 

모든 BFS 탐색이 끝난 뒤에는 저장된 최소 값을 반환하여 출력하도록 합니다. 

전체 코드

import sys
from collections import deque
from queue import PriorityQueue

#위, 아래,오른쪽, 왼쪽
dcol = [0, 0, 1, -1]
drow = [1, -1, 0, 0]

# 벽 검사
def isRange(row, col):
	if col >= w or col < 0: return False
	if row >= h or row < 0: return False
	return True

def bfs() :
	#(h, w, defence)
	queue = deque()
	queue.append((0, 0, 0))

	#(h,w)
	visit[0][0] = True
	result_m = 999999999

	while queue:
		sh,sw,sdefence = queue.popleft();

		#queue에서 꺼낸 좌표가 h-1,w-1일 경우 
		if sh == h - 1 and sw == w - 1:
			result_m = min(result_m, sdefence)

		for i in range(4):
			nh = sh + drow[i]
			nw = sw + dcol[i]
			ndefence = sdefence

			if isRange(nh, nw) == False :
				continue

			# 벽이 없는 경우
			if maps[nh][nw] == '0' and visit[nh][nw]== False:
				visit[nh][nw] = True
				queue.appendleft((nh, nw, ndefence))

			# 벽이 있는 경우
			elif maps[nh][nw] == '1' and visit[nh][nw]== False:
					visit[nh][nw] = True
					queue.append((nh, nw, ndefence+1))
	return result_m

#입력
w, h = map(int, sys.stdin.readline().split())
maps = [sys.stdin.readline().rstrip() for _ in range(h)]
visit = [[False]*w for _ in range(h)]

#결과 출력
result = 0
result = bfs()
print(result)

파이썬 / BOJ 백준 알고리즘 / 2206번 벽 부수고 이동하기 - BFS

www.acmicpc.net/problem/2206

문제 풀이 

2206번 벽 부수고 이동하기 문제는 BFS로 풀 수 있는 문제입니다. 

Queue에 (h, w, defence, cnt)를 넣고, bfs를 돌립니다. 

그리고 visit[h][w][defence]를 만들어, 방문했는지를 기록합니다. defence는 벽을 한번 통과 했는지, 통과하지 않았는지에 대한 정보입니다 .

Queue에 있는 정보를 꺼내었을 때, 위,아래,왼쪽,오른쪽을 검색하면서, 벽이 없다면 방문했는지를 검사하고 그 좌표를 Queue에 넣어줍니다. 벽이 있다면, 현재 벽을 한번 뚫었는지 검사하여, 한번도 뚫지 않았다면, 방문했는지 검사하고 그 좌표를 Queue에 넣어줍니다. Queue에 넣어줄 때에는 cnt를 +1해줍니다. 

Queue에 있는 정보를 꺼내었을 때, 입력한 N, M 값이면 cnt를 반환하여 출력합니다. 

Queue가 비어있는데, cnt를 반환하지 못하였다면 -1를 출력해줍니다. 

전체 코드

import sys
from collections import deque

#위, 아래,오른쪽, 왼쪽 
dcol = [0, 0, 1, -1]
drow = [1, -1, 0, 0]

# 벽 검사
def isRange(row, col):
	if col >= w or col < 0: return False
	if row >= h or row < 0: return False
	return True

def bfs() :
	#(h, w, defence, count)
	queue = deque()
	queue.append((0, 0, 1, 1))

	#(h,w,defence)
	visit[0][0][1] = True

	while queue:
		sh,sw,sdefence,scnt = queue.popleft();

		#queue에서 꺼낸 좌표가 h-1,w-1일 경우 결과값 반환
		if sh == h - 1 and sw == w - 1:
			return scnt

		for i in range(4):
			nh = sh + drow[i]
			nw = sw + dcol[i]
			ndefence = sdefence
			ncnt = scnt + 1

			if isRange(nh, nw) == False :
				continue
			
			# 벽이 없는 경우 
			if maps[nh][nw] == '0' and visit[nh][nw][ndefence] == False:
				visit[nh][nw][ndefence] = True
				queue.append((nh, nw, ndefence, ncnt))
				
			# 벽이 있는 경우
			elif maps[nh][nw] == '1' and visit[nh][nw][ndefence] == False:
				if ndefence == 1: #벽을 한번 뚫었는지 검사
					ndefence = 0
					visit[nh][nw][ndefence] = True
					queue.append((nh, nw, ndefence, ncnt))
	return -1

h, w = map(int, sys.stdin.readline().split())
maps = [sys.stdin.readline().rstrip() for _ in range(h)]
visit = [[[False]*2 for _ in range(w)] for _ in range(h)]

result = 0
result = bfs()
print(result)

파이썬 / BOJ 백준 알고리즘 / 1697번 숨바꼭질 - BFS

www.acmicpc.net/problem/1697

문제 풀이

1697 숨바꼭질 문제는 BFS를 이용해 풀 수 있는 문제입니다. 

각 위치까지 몇초가 걸리는지에 대한 정보를 넣을 1차원 배열을 하나 만듭니다. 

그리고 현재 점을 Queue에 넣으면서 BFS를 동작시킵니다. 

BFS를 동작시킬 때, 아래 3가지 동작이 이루어지도록 하고, 이동된 위치를 Queue에 넣습니다. 

1) 1초 후에 X-1로 이동 (단, X-1이 0보다는 크거나 작아야 됩니다.)

2) 1초 후에 X+1로 이동 (단, X+1이 200000보다는 같거나 작아야 합니다.)

3) 1초 후에 2*X로 이동 (단, X*2가 200000보다는 같거나 작아야 합니다.)

그리고 이동된 위치를 Queue에 넣을 때, 해당 위치에 대한 시간정보를 넣어서, 중복 방문하지 않도록 하고, 이 시간 정보는 다음 위치를 위해 계속 사용됩니다. 

Queue에 pop할 때, pop한 위치가 동생이 있는 위치라면, 배열에서 그 위치에 있는 시간 정보를 출력하면 이 문제가 해결됩니다. 

전체 코드

import sys
from collections import deque

N,K = map(int, sys.stdin.readline().split())
arr = [0]*200001

queue = deque()
queue.append((N))

result = 0
while queue:
    next = queue.popleft()

    if next == K:
        result = arr[next]
        break
    if next-1 >= 0 and arr[next-1] == 0:
        arr[next-1] = arr[next] + 1
        queue.append((next - 1))
    if next+1 <= 200000 and arr[next+1] == 0:
        arr[next+1] = arr[next] + 1
        queue.append((next + 1))
    if next*2 <= 200000 and arr[next*2] == 0:
        arr[next*2] = arr[next] + 1
        queue.append((next * 2))

print(result)

파이썬 / BOJ 백준 알고리즘 / 7576번 토마토 - BFS

www.acmicpc.net/problem/7576

문제 풀이 

 7576번 토마토 문제는 BFS로 풀 수 있습니다. 

이 문제를 풀기 위한 핵심음 아래와 같습니다. 

1. BFS에서 list보다는 queue(deque)를 사용하는 것이 동작 시간이 훨씬 빠릅니다. 

2. 상자의 토마토들의 정보를 한줄 입력할 때마다 토마토가 있으면(값이 1이면), Queue에 넣습니다. 

3. BFS 동작을 할 때에 pop을 한 좌표의 값에 1 증가한 값을 push 해주는 좌표의 값에 넣어주고, 마지막에 pop되는 값을 반환합니다. 

4. BFS 동작을 모두 끝내고, 배열의 모든 값을 검사하면서 0이 있는지 검사합니다. 

전체 코드

import sys
from collections import deque

dcol = [0, 0, 1, -1]
drow = [1, -1, 0, 0]

def isRange(row, col):
	if col >= w or col < 0: return False
	if row >= h or row < 0: return False
	return True

def show():
	for i in range(h):
		for j in range(w):
			print(maps[i][j], end=" ")
		print()

def bfs() :
	max = 0
	while queue:
		srow, scol = queue.popleft()

		for i in range(4):
			nrow = srow + drow[i]
			ncol = scol + dcol[i]

			if isRange(nrow, ncol) == False:
				continue
			if maps[nrow][ncol] != 0:
				continue
			#show()

			maps[nrow][ncol] = maps[srow][scol] + 1
			if max < maps[nrow][ncol]:
				max =  maps[nrow][ncol]
			queue.append((nrow, ncol))

	return max - 1


queue = deque()
maps = []
w,h = map(int, sys.stdin.readline().split())

for i in range(h):
	line = []
	line = list(map(int, sys.stdin.readline().split()))
	maps.append(line)
	for j in range(w):
		#print(" i = ", i , " , j = ", j , ", maps = ", maps[i][j])
		if line[j] == 1:
			queue.append((i, j))
result = 0
result = bfs()
if result == -1:
	result = 0

for i in range(h):
	if 0 in maps[i]:
		result = -1
		break
print(result)