봉천동 적토마

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

1. BFS문제인데 DP로 생각했다.
2. 우선순위큐를 활용한 BFS라 신기했다. 

처음 풀때 

이런식으로 하나씩 쓰다보면서 규칙을 발견해보려고 했다. 

짝수인경우) X_i = min( X_i/2 , X_i-1 + 1) 

홀수인경우) X_i = X_i-1 + 1 

이라는 점화식을 세웠다. 

subin, target = map(int, input().split())

d = [-1] * 100002
d[subin] = 0
d[subin+1] = 1
for i in range(subin+2, target+1) : 
    if i%2 == 0 and d[i//2] != -1: 
        d[i] = min(d[i//2], d[i-1]+1)
    else :
        d[i] = d[i-1] + 1

print(d[target])

근데 

하하하!

로그 찍어보니까 

이렇게 나왔다. 최적값을 제대로 못 구하고 있음을 알 수 있다. 

두배수로 점프하는게 가장 적은 값인데, 이걸 한번 배열 전체에 기록을 하고, 또 이걸기반으로 또 배열 전체를 기록을 하는 식으로 진행해야 최적값을 제대로 구할 수 있음을 알게 됐다. (나는 배열 전체를 한번만 검색하는 식으로 만들어서,, 최적값이 나올 수 가 없었다.) 

그래서 검색하니까 DP가 아니라 BFS 더라 .. ^^

오해해서 미안했다..

이렇게 우선순위 큐를 돌리면 빠르게 최적값을 찾아낼 수 있다!!

이런식의 우선순위큐를 활용한 BFS도 있군아 재밌다

최종 코드

from collections import deque 

def bfs() :
    graph = [-1] * 100001
    graph[subin] = 0
    que = deque([subin])

    while que :
        target = que.popleft()
        
        # 동생 위치에 도달시(정답발견)
        if target == sister :
            return graph[target]
        
        for i in (target+1, target-1, target*2) : # 세가지 방법을 순서대로 진행
            # 이동하는 곳이 범위내이며 / 한번도 방문하지 않았으면
            if 0<=i<=100000 and graph[i] == -1 :
                # 순간이동인경우
                if i == target*2 :
                    graph[i] = graph[target]
                    que.appendleft(i) # 순간이동이니까 먼저 탐색
                else :
                    graph[i] = graph[target] + 1
                    que.append(i)

subin, sister = map(int, input().split())
print(bfs())

굿!

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

기본 BFS이지만, 복수의 시작점을 가진 BFS에 대해 다시 한번 생각해보는 계기가 됐다. 

from collections import deque 


m, n = map(int,input().split())
graph = []
for _ in range(n) : 
    graph.append(list(map(int, input().split())))

dx, dy = [-1, 1, 0, 0], [0, 0, -1 ,1]

q = deque([]) # queue 생성

for i in range(n) : 
    for j in range(m) : 
        if graph[i][j] == 1 : 
            q.append((i, j)) 

def bfs(): 
    while q : 
        x, y = q.popleft()
        for i in range(4) :
            _x, _y = x+dx[i], y+dy[i]
            if 0<=_x<n and 0<=_y<m and graph[_x][_y] == 0 : 
                graph[_x][_y] = graph[x][y] + 1
                q.append((_x, _y))

bfs() 

is_done = True
res = -1
for i in range(n) : 
    for j in range(m) : 
        if graph[i][j] == 0 : # 한개라도 익지 못한 토마토가 있으면 = 토마토가 모두 익지는 못하는 상황 = -1을 출력
            is_done = False
        res = max(res, graph[i][j])

if is_done : 
    print(res-1)
else :
    print(-1)

처음에는 각자 다른 시작점을 가진 BFS를 어떡하지...? 생각했는데

queue에 들어가는 순서를 유심히 생각해보니

그냥 순서대로 시작점(1)가 popleft되어도, 시작점에서 "1만큼씩만" 체크하고, 다시 다음시작점이 popleft된다. 

그래서 한개의 큐만 써도 됐다. 와~! 

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

기본적인 BFS

from collections import deque

n = int(input())
graph = []

for _ in range(n) : 
    graph.append(list(map(int , input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS로 영역크기 구하기
def bfs(start) : 
    res = 0 # 영역크기
    q = deque([start])
    graph[start[0]][start[1]] = 0 # 방문처리
    while(q) :
        x, y = q.popleft()
        graph[x][y] = 0
        res += 1
        for i in range(4) : 
            _x, _y = x + dx[i], y + dy[i]
            if 0<=_x<n and 0<=_y<n :
                if graph[_x][_y] == 1 :
                    graph[_x][_y] = 0
                    q.append((_x, _y))
    return res

danji_info = []
for i in range(n) : 
    for j in range(n) : 
        if graph[i][j] == 1 : # 1을 만나면 
            danji_cnt = bfs((i, j)) # BFS로 영역 구하기
            if danji_cnt != 0 : 
                danji_info.append(danji_cnt)

danji_info.sort() # 오름차순 정렬
print(len(danji_info))
for d in  danji_info: 
    print(d)

기본적인 BFS였다!

백준 16234 인구이동 (브론즈)

분기가 까다로운 시뮬레이션 -> 쉽다고 대충손만 놀리다가 더 귀찮아짐
+ BFS로 영역찾기 

처음 문제를 읽고

시뮬레이션이라서 크게 어떤 함수가 어디에 어떻게 쓰일것인지 구상해봤다.

# 데이터 입력받기
N, L, R = map(int, input().split())
graph = []
for _ in range(N) : 
    graph.append(list(map(int, input().split())))




dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
visited = [[0]*N for _ in range(N)]
visted_cnt = 1
# 연합이 될 수 있는 국가를 visited 그래프에 1,2,3,4... 연합국등으로 체크하기 
def search_union(i, j) :
    
    


# 연합을 이루고 있는 국가들간 국경선 개방하고, 인구수 계산한 결과로 초기화하기
def calc() :





day_cnt = 0
while(True) : 

    for i in range(N) :
        for j in range(N) :
            if(search_union(i, j)) : continue
            else : break # 더이상 인구이동이 없을때
    calc()
    day_cnt += 1
   


print(day_cnt)

이제 여기 빈칸에 맞게 차근차근 짜다보면 되겠징

코드

from collections import deque


# 데이터 입력받기
N, L, R = map(int, input().split())
graph = []
for _ in range(N) : 
    graph.append(list(map(int, input().split())))

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


# 연합이 될 수 있는 국가를 BFS로 탐색하여 번호 리스트를 리턴
def search_union(start_x, start_y) :
    union_list = [(start_x, start_y)]
    q = deque([(start_x, start_y)])    
    while(q) :
        x, y = q.popleft()
        visited[x][y] = True
        for i in range(4) : 
            _x, _y = x + dx[i], y + dy[i]
            if _x<0 or _x>= N or _y<0 or _y>=N : # 범위 벗어남
                continue
            if visited[_x][_y] == False :    
                if L <= abs(graph[_x][_y] - graph[x][y]) <= R : 
                    q.append((_x, _y))
                    visited[_x][_y] = True
                    union_list.append((_x, _y))
    return union_list
                      
day_cnt = 0         
while (True) :
    # 하루가 지나면 visited와 연합 리스트 리셋!
    visited = [[False]*N for _ in range(N)]
    done_flag = True
    for i in range(N) :
        for j in range(N) :
            if visited[i][j] == False : 
                area_list = search_union(i, j) # 해당 국가와 연합인 국가의 리스트 얻어옴
                if len(area_list) > 1 : 
                    done_flag = False
                    mean_result = sum([graph[x][y] for x, y in area_list]) // len(area_list)
                    for x, y in area_list :
                        graph[x][y] = mean_result   # 평균 인구로 초기화해준다
    if (done_flag) : break  # 그래프의 모든 칸들 중 연합인 국가들이 하나도 없으면 인구이동이 불가능한 상태
    day_cnt += 1 

print(day_cnt)

느낀점 

- flag같은거 안쓰고 논리적 분기로(?) 최대한 깔끔하게 만들고 싶었는데..  그러려는 생각이 더 복잡하게 만든 것 같다

- 그래서 처음에 생각해둔 덩어리대로 만들어 지지 않았다

- 하루가 지나면 리셋된다는거 -> 이거의 기준을 헷갈리지 말자

- 시뮬레이션은 아 ~ 껌이네~ 이러다가 결국 너무 시간이 많이걸린다... 자주 하자 ㄱ-