해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 2178번 미로 탐색 - BFS

문제 풀이

이 문제는 BFS로 풀 수 있는 문제입니다. 

(1,1)을 BFS의 queue에 넣고, (1,1)의 위,아래,왼쪽,오른쪽을 검색하여 그 좌표의 값이 1인 경우 그 좌표를 queue에 넣습니다. 그 좌표에 대한 값은 (1,1)의 값에 +1한 값을 넣어줍니다. 

이것을 반복하고, 검색 대상의 좌표가 (N,M)이 되면, 검색하는 값의 +1한 값을 반환합니다. 

그 반환되는 값을 출력하면 이 문제가 해결됩니다. 

위의 과정이 동작된다면, 예제 1번은 아래와 같이 배열의 값들이 계산됩니다.

(N,M)의 값은 검색하는 값인 14의 +1한 값이 되어, 15로 반환됩니다.

 예제 4번은 아래와 같이 배열의 값들이 계산됩니다.

전체 코드

import sys

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(row, col) :
	queue = [(row, col)]

	while queue:
		srow, scol = queue.pop(0)

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

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

			#print ("nrow = ", nrow, ", ncol = ", ncol)
			#show()

			if nrow == h-1 and ncol == w-1:
				return maps[srow][scol] + 1

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



#입력
h,w = map(int, sys.stdin.readline().split())
maps = [list(map(int, input())) for _ in range(h)]

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

파이썬 / BOJ 백준 알고리즘 / 4963번 섬의 개수 - BFS

문제 풀이

이 문제는 bfs 또는 dfs로 풀 수 있는 문제입니다. 

이번에는 bfs로 이 문제를 풀어 보도록 하겠습니다. 

입력 값을 maps에 list 형태로 넣습니다. 

그리고 maps를 전체 검색하며, maps[i][j]에 값이 1이면, 새로운 섬이라는 뜻으로, bfs를 돌리고, result를 1 증가시킵니다.

마지막에 result의 값을 출력합니다. 

	for i in range(0, h):
		for j in range(0, w):
			if maps[i][j] == 1:
				bfs(i, j)
				result += 1
	print(result)

bfs 함수에서는 전달인자로 들어온 row, col에 대하여 maps[row][col] 값을 0으로 만들고, queue에 넣습니다. 

queue에 쌓여진 것 중에 가장 먼저 들어온 것을 빼내어, 그 row, col을 기준으로 8 방향(위, 아래, 왼쪽, 오른쪽, 대각선)을 검색하여, 땅이 있는 곳(maps[][]의 값이 1인 곳)을 0으로 만듭니다. 

그러면 섬 하나의 지점의 값이 bfs로 들어오면, 이어진 모든 섬의 값이 0으로 변경됩니다. 

def bfs(row, col) :
	num = 0
	queue = [(row, col)]
	maps[row][col] = 0

	while queue:
		srow, scol = queue.pop(0)

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

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

			maps[nrow][ncol] = 0
			queue.append((nrow, ncol))

전체 코드

import sys

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

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

def bfs(row, col) :
	num = 0
	queue = [(row, col)]
	maps[row][col] = 0

	while queue:
		srow, scol = queue.pop(0)

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

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

			maps[nrow][ncol] = 0
			queue.append((nrow, ncol))


while True:
	# 입력 및 변수 설정
	w,h = map(int, sys.stdin.readline().split())
	if w == 0 and h == 0:
		break
	maps = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]
	result = 0

	# 검색 및 bfs 돌리기
	for i in range(0, h):
		for j in range(0, w):
			if maps[i][j] == 1:
				bfs(i, j)
				result += 1
	print(result)

파이썬 / BOJ 백준 알고리즘 / 2667번 단지번호붙이기  - BFS

문제 풀이

이 문제는 BFS 또는 DFS로 풀 수 있는 문제입니다. 

list 형태로 되어 있는 maps에 (0,0) 부터 검색을 시작합니다. 

그 maps의 값이 0이면 skip하고, 1이면 bfs를 돌립니다. 

bfs 함수의 반환값으로 그 단지의 집의 수를 받아오면 result에 넣습니다. 

bfs를 돌릴 때, 전달인자로 row, col을 넘겨주고, 해당 maps[row][col]은 0으로 만들어 줍니다. 

그리고 그 row, col은 queue에 넣습니다. 

이제 while문을 돌려 queue에 있는 것을 하나씩 뺍니다. (queue.pop)

그 queue에서 pop한 row, col의 위, 아래, 오른쪽, 왼쪽을 검사하여, maps의 범위 안에 있고, maps[row][col]의 값이 0이 아니라면, 해당 row, col을 queue에 넣습니다. 

이러한 과정을 반복하면 하나의 연결된 단지의 집을 구할 수 있습니다. 

전체 코드 - BFS

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

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

def bfs(row, col) :
	num = 0
	queue = [(row, col)]
	maps[row][col] = 0

	while queue:
		srow, scol = queue.pop(0)
		num += 1

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

			# maps의 범위가 아니라면 skip
			if isRange(nrow, ncol) == False:
				continue
            # 해당 row, col 값에 대한 maps의 값이 0이면 skip
			if maps[nrow][ncol] == 0:
				continue

			maps[nrow][ncol] = 0
			queue.append((nrow, ncol))

	return num;


#입력 및 변수 설정
N = int(input())
cnt = 0
maps = [list(map(int, input())) for i in range(N)]
result = []

# bfs로 각 단지수 구하기
for i in range(0, N):
	for j in range(0, N):
		if maps[j][i] == 1:
			result.append( bfs(j,i))

#결과 출력
result.sort()
print(len(result))
for i in result :
	print(i)

www.acmicpc.net/problem/2667

파이썬 / 백준 알고리즘 / 1260번 DFS와 BFS 문제 및 풀이

https://www.acmicpc.net/problem/1260

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 및 출력

문제 풀이

너비우선탐색(BFS, Breadth First Search)와 깊이우선탐색(Depth First Search)의 전형적인 기초 문제입니다. 이 두 알고리즘은 그래프를 탐색하기 위한 알고리즘으로 모든 정점을 탐색하기 위해 사용됩니다.

DFS는 한 경로로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 경로로 탐색하는 방식이고,(스택의 방식을 이용함, 스택은 기본 동작이라 스택 자료 구조를 이용할 필요는 없음)
BFS는 갈림길에 연결되어 있는 모든 경로를 한번씩 탐색한 뒤 다시 연결되어 있는 모든 경로를 넓게 탐색하는 방식입니다. (자료 구조 큐 또는 덱 구조를 이용해야 함)

예를 들어 아래와 같은 그래프에서 DFS 동작은 다음과 같습니다. 
1) 정점 1에서부터 검색 시작
2) 1에 연결된 정점 2,3,4 중 가장 작은 수인 2(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨)를 방문
3) 2에 연결된 정점 4를 방문
4) 4에 연결된 정점 3을 방문
5) 더이상 방문할 정점이 없으므로 종료
- 결국 1->2->4->3 순으로 방문하게 됩니다

예를 들어 아래와 같은 그래프에서 BFS 동작은 다음과 같습니다.
1) 정점 1에서부터 검색 시작 
2) 정점 1과 연결된 2를 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
3) 정점 1과 연결된 3을 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
4) 정점 1과 연결된 4를 검색 
- 결국 1->2->3->4 순으로 방문하게 됩니다. 

전체 코드

from collections import deque

def dfs(v):
    print(v, end=' ')
    visit[v] = 1
    for i in range(1, n + 1):
        if visit[i] == 0 and adj[v][i] == 1:
            dfs(i)

def bfs(v):
    queue = deque()
    visit[v] = 1
    queue.append(v)

    while (queue):
        v = queue.popleft()
        print(v, end=' ')
        for i in range(1, n + 1):
            if visit[i] == 0 and adj[v][i] == 1:
                queue.append(i)
                visit[i] = 1

#입력 n : 정점의 개수, m : 간선의 개수, v : 탐색을 시작할 정점의 번호
n, m, v = map(int, input().split())
adj = [[0] * (n + 1) for i in range(n + 1)]
visit = [0 for i in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    adj[x][y] = 1
    adj[y][x] = 1

#출력
dfs(v)
print()

visit = [0 for i in range(n + 1)]
bfs(v)