해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 1525번 퍼즐 - BFS

www.acmicpc.net/problem/1525

문제 풀이

1525번 퍼즐 문제는 BFS(너비 우선 탐색)으로 풀 수 있는 문제입니다. 

퍼즐의 2차 배열 값을 문자열로 변환하여, 이 문자열을 가지고 BFS 탐색을 합니다. 

위에 변환된 문자열을 가지로 BFS 탐색을 할 때에, 배열에서 0을 기준으로 왼쪽,오른쪽,위,아래에 값을 교환하고, 그 배열의 값을 문자열로 변환시켜 queue에 넣습니다. 

queue에 넣은 문자열을 뺐을 때, 그 문자열이 '123456780'과 동일하다면 BFS 탐색을 종료하고, 이동 횟수를 반환하도록 합니다. 그 문자열이 '123456780'과 같지 않다면 또 0을 기준으로 왼쪽,오른쪽,위,아래에 값을 교환하여 탐색을 진행합니다. 

아래 코드는 문자열에서 '0'의 위치를 찾아, 왼쪽, 오른쪽, 위, 아래 값과 교환한 문자열을 만드는 부분으로 핵심 코드입니다. (puzzle_c -> puzzle_n으로 변경 )

그리고 주의할 점은 방문한 정보를 list 또는 queue에 넣을 수도 있는데, 시간 초과가 발생합니다. 

방문한 정보를 dictionary 자료 구조에 넣어 검색 속도를 빠르게 할 필요가 있습니다.  

#dictionary로 생성
visit = dict()

# 방문하지 않았다면, dictionary에 추가 
if not visit.get(puzzle_n):
	visit[puzzle_n] = 1
	queue.append((puzzle_n, time + 1))

전체 코드 

import sys
from collections import deque

#서, 북, 동, 남
dcol = [-1,  0, 1,  0]
drow = [0,  -1, 0,  1]

# s 문자열의 n번 항과 k번 항의 값을 교환
def swap(s, n, k):
    l = s[n]
    m = s[k]
    s = s[:k] + l + s[k+1:]
    s = s[:n] + m + s[n+1:]
    return s
# 벽 검사
def isRange(row, col):
	if col >= 3 or col < 0: return False
	if row >= 3 or row < 0: return False
	return True

def bfs(puzzle_s):
    result = -1
    queue = deque()
    queue.append((puzzle_s, 0))
    visit[puzzle_s] = 1

    while queue:
        puzzle_c, time = queue.popleft()

        #print(puzzle_c)
        if puzzle_c == target:
            result = time
            break
        pos = puzzle_c.find('0')
        row = pos//3
        col = pos%3
        #print("pos = ", pos, ", row = ", row, ", col = ", col)

        # 서, 북, 동, 남 방향으로 탐색
        for i in range(4):
            nrow = row + drow[i]
            ncol = col + dcol[i]

            #print("pos = ", pos, ", nrow = ", nrow, ", ncol = ", ncol)
            if isRange(nrow, ncol) is False:
                continue

            puzzle_n = puzzle_c
            puzzle_n = swap(puzzle_n, pos, nrow*3 + ncol)
            #print("new puzzle : ", puzzle_n)

            #방문했는지 검사, 방문하지 않았다면 visit 추가 및 queue에 문자열 추가
            if not visit.get(puzzle_n):
                visit[puzzle_n] = 1
                queue.append((puzzle_n, time + 1))
    return result

puzzle = ""
visit = dict()
for i in range(3):
	line = []
	line = list(map(int, sys.stdin.readline().split()))
	puzzle += str(line[0]) + str(line[1]) + str(line[2])

target = '123456780'
result_m = 0
result_m = bfs(puzzle)
print(result_m)

파이썬 / BOJ 백준 알고리즘 / 2234번 성곽 - BFS

www.acmicpc.net/problem/2234

문제 풀이

2234번 성곽 문제는 BFS로 풀 수 있는 문제입니다. 

성벽은 서,북,동,남 순서로 되어 있고, 벽의 정보는 각각 1,2,4,8입니다.

비트마스킹을 이용하여, 성벽의 유무를 판단하도록 합니다. 

서쪽에 벽이 없다면, 서쪽으로 이동하여 BFS 탐색을 이어나가고, 

북쪽에 벽이 없다며, 북쪽으로 이동하여 BFS 탐색을 이어나가고, 

동쪽에 벽이 없다며, 동쪽으로 이동하여 BFS 탐색을 이어나가고, 

남쪽에 벽이 없다며, 남쪽으로 이동하여 BFS 탐색을 이어나갑니다. 

해당 내용은 아래 알고리즘을 참고하시면 되고, 이 부분이 핵심 코드입니다.

		for k in range(4): # 0 - 서, 1 - 북, 2 - 동, 3 - 남
			if maps[ey][ex] & (1<<k) == 0:
				nx = dcol[k] + ex
				ny = drow[k] + ey

				if isRange(ny, nx) is False:
					break

				if visit[ny][nx] is False:
					visit[ny][nx] = True
					queue.append((ny, nx))
					r += 1

우선, 1) 이 성에 있는 방의 개수는 전체 성의 좌표를 돌면서 BFS 탐색을 호출하는 부분의 개수를 계산하여 구합니다. 

BFS 탐색을 한번 돌리면 연결되어 있는 통로는 모두 방문하게 되어, BFS 탐색을 호출하는 부분은 다른 방이 있을 때마다 호출하게 되기 때문입니다. 

2) 가장 넓은 방의 넓이는 BFS 탐색을 할 때, 반환되는 방의 크기 중 가장 큰 크기를 계산하여 구합니다. 

BFS 탐색을 할 때, 연결된 방의 좌표를 Queue에 넣을 때마다 방의 개수를 증가시키고, BFS의 탐색이 종료되면 이 방의 모든 개수를 반환하게 됩니다. 

3) 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기는 벽을 하나씩 제거해 보면서, 각 방의 크기를 구하고, 그 중 가장 큰 방을 계산하여 구합니다.

전체 코드

import sys
from collections import deque

#서, 북, 동, 남
dcol = [-1,  0, 1,  0]
drow = [0,  -1, 0,  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):
	queue = deque()

	#(출발점 row, 출발점 col)
	queue.append((row, col))
	visit[row][col] = True
	r = 1

	while queue:
		ey, ex = queue.popleft()
		#print("row = ", row, ",col = ", col, ", ey = ", ey , ", ex = ", ex)

		for k in range(4):
			if maps[ey][ex] & (1<<k) == 0:
				nx = dcol[k] + ex
				ny = drow[k] + ey

				if isRange(ny, nx) is False:
					break

				if visit[ny][nx] is False:
					visit[ny][nx] = True
					queue.append((ny, nx))
					r += 1
	return r


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

for i in range(h):
	line = []
	line = list(map(int, sys.stdin.readline().split()))
	maps.append(line)

# 방의 개수
room_number = 0

# 가장 넓은 방의 넓이
room_size = 0
visit = [[False]*w for _ in range(h)]

for i in range(h):
	for j in range(w):
		if visit[i][j] is False:
			room_number += 1
			room_size = max(room_size, bfs(i,j))

print(room_number)
print(room_size)

# 하나의 벽을 제거하여 l을 수 있는 가장 넓은 방의 크기
room_size_one_brick = 0
for i in range(h):
	for j in range(w):
		for k in range(4):
			if maps[i][j] & (1<<k) == (1<<k):
				visit = [[False] * w for _ in range(h)]
				maps[i][j] -= (1<<k)
				room_size_one_brick = max(room_size_one_brick, bfs(i,j))
				maps[i][j] += (1<<k)
print(room_size_one_brick)

파이썬 / BOJ 백준 알고리즘 / 14226번 이모티콘 - BFS

www.acmicpc.net/problem/14226

문제 풀이

14226번 이모티콘 문제는 BFS로 풀 수 있는 문제입니다. 

2차 배열을 만들어 visit[화면에 있는 이모티콘][클립보드에 있는 이모티콘]에 걸린시간을 넣어주도록 합니다.

그리고 BFS 탐색을 할 때, (화면에 있는 이모티콘, 클립보드에 있는 이모티콘, 걸린 시간) 세트로  Queue에 넣어줍니다. 

BFS 탐색은 아래 문제에 있는 내용으로 하도록 합니다.

1.화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2.클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3.화면에 있는 이모티콘 중 하나를 삭제한다.

탐색을 종료하는 시점은 입력된 S의 값과 Queue에서 꺼낸 화면에 있는 이모티콘의 값과 일치하게 되면 걸린 시간을 반환하여 출력하도록 합니다. 

전체 코드

import sys
from collections import deque

def bfs() :
	visit = [[0]*2001 for _ in range(2001)]
	queue = deque()

	# ( screen, clipboard, time)
	queue.append((1, 0, 0))

	result_m = 987654321

	while queue:
		sS,sC,sT = queue.popleft();

		if sS == S:
			result_m = min(result_m, sT)
			break

		nT = sT + 1
		nC = sS
		# 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장
		#print("sS = ", sS, ", sC = ", sC, ", sT = ", sT, ", nT = ", nT, ", nC = ", nC)

		if 0 < sS <=1000 and (visit[sS][nC] > sT or visit[sS][nC] == 0):
			visit[sS][nC] = nT
			queue.append((sS, nC, nT))

		# 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
		nS = sS + sC
		#print("sS = ", sS, ", sC = ", sC, ", sT = ", sT, ", nT = ", nT, ", nC = ", nC, ", nS = ",nS)
		if nS <= 2*S and (visit[nS][sC] > sT or visit[nS][nC] == 0):
			visit[nS][sC] = nT
			queue.append((nS, sC, nT))

		#화면에 있는 이모티콘 중 하나를 삭제한다.
		nS = sS - 1
		if sS -1 > 0 and (visit[nS][sC] > sT or visit[nS][nC] == 0):
			visit[nS][sC] = nT
			queue.append((nS, sC, nT))

	return result_m

S = int(input())
result = 0
result = bfs()
print(result)

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

www.acmicpc.net/problem/13549

문제 풀이

13549번 숨바꼭질 3 문제는 BFS로 풀 수 있는 문제입니다. 

아래 1697번 숨바꼭질의 약간 변형된 문제입니다. 

아래 숨바꼭질과 다른 점은 2*X에 가중치를 주어 appendleft() 함수를 사용하고, queue에서 먼저 탐색되도록 합니다. 

그리고 2*X로 탐색된 곳은 0초가 걸리기 때문에, 시간 정보를 넣을 때에는 이전의 시간 정보와 동일하게 넣습니다. 

이렇게 한다면 목적지까지의 가장 빠른 시간을 구할 수 있습니다.

zidarn87.tistory.com/248

전체 코드

import sys
from collections import deque


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

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

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

    if next == K:
        result = arr[next]
        break
    
    # *2
    if next*2 <= 100000 and visit[next*2] == False:
        arr[next*2] = arr[next]
        queue.appendleft((next * 2))
        visit[next*2] = True
    # -1
    if next-1 >= 0 and visit[next-1] == False:
        arr[next-1] = arr[next] + 1
        queue.append((next - 1))
        visit[next - 1] = True
    
    # +1
    if next+1 <= 100000 and visit[next+1] == False:
        arr[next+1] = arr[next] + 1
        queue.append((next + 1))
        visit[next + 1] = True


print(result)