24.07.31 알고리즘 풀이(BFS)

오늘은 건강상의 이슈로.. 공부를 하지 못하였습니다. 저녁 쯤엔 좀 괜찮아져서 어제 공부했던 BFS 3문제라도 풀었다.

그리구 올림픽 때문에 공부에 집중을 하지 못하고 있슴...대한민국 화이팅..ㅜㅜ

---

알고리즘수업- 너비우선탐색2

 

이 문제는 어제 풀었던 알고리즘수업 - 너비우선탐색1 문제와 똑같다. 다른 점은 인접 정점은 내림차순으로 방문한다는 점밖에 없다. 그래서 sort(reverse=True) 를 사용하여 graph를 내림차순으로 정렬해주었다.

import sys
from collections import deque
input = sys.stdin.readline

N,M,R = map(int,input().split())
graph = [[] for _ in range(N+1)]
visited_bfs = [0] * (N+1)
cnt = 1

for _ in range(M):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(N+1):
    graph[i].sort(reverse=True)

def bfs(x):
    q = deque()
    q.append(x)
    global cnt 
    visited_bfs[x] = cnt
    
    while q:
        x_ = q.popleft() 

        for i in graph[x_]:
            if visited_bfs[i] == 0:
                q.append(i)
                cnt += 1
                visited_bfs[i] = cnt

bfs(R)
for i in visited_bfs[1:]:
    print(i)

 

미로탐색

 

이 문제는 (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다.

입력 사항에서 각각의 수들은 붙어서 입력으로 주어진다라는 부분이 있어서 입력을 strip() 함수를 사용하여 개행문자를 기준으로 분리해서 입력받았다.

 

<틀린 답안>

import sys
from collections import deque
input = sys.stdin.readline

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

def bfs(x,y):
    q = deque()
    q.append((x,y))
    graph[x][y] = 0
    cnt = 1

    while q:
        x_ , y_ = q.popleft()
        
        for i in range(4):
            nx = x_ + dx[i]
            ny = y_ + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= M or graph[nx][ny] == 0:
                continue

            if graph[nx][ny] == 1:
                q.append((nx,ny))
                graph[nx][ny] = 0
                cnt += 1 

            if nx == N-1 and ny == M-1:
                return cnt

N,M = map(int,input().split())
graph = [ list(map(int,input().strip())) for _ in range(N)]

print(bfs(0,0))

 

처음에 이런식으로 풀이를 하였는데 출력값이 제대로 나오지 않았다. 알고보니 내가 입력한 답안은 cnt 변수를 사용하여 탐색한 노드의 수를 세기 때문에 최단 경로 길이를 나타내지 않고 있었다.

최단 경로 길이를 제대로 계산하기 위해서는 각 노드에 도달할 때의 이동 횟수를 기록해야 한다. 

그래서 각 노드에 도달할 때 graph의 값을 방문 표시를 이동 횟수로 저장하도록 변경하여야 했다.

 

<수정된 코드>

import sys
from collections import deque
input = sys.stdin.readline

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

def bfs(x,y):
    q = deque()
    q.append((x,y))
    graph[x][y] = 1

    while q:
        x_ , y_ = q.popleft()
        
        for i in range(4):
            nx = x_ + dx[i]
            ny = y_ + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= M or graph[nx][ny] == 0:
                continue

            if graph[nx][ny] == 1:
                q.append((nx,ny))
                graph[nx][ny] = graph[x_][y_] + 1

            if nx == N-1 and ny == M-1:
                return graph[nx][ny]

N,M = map(int,input().split())
graph = [ list(map(int,input().strip())) for _ in range(N)]

print(bfs(0,0))

 

 

전쟁-전투

 

color 구분을 bfs 함수 안에서 해야되는 줄 알고 안에서 하려했으나 방법을 모르겠어서 예전에 풀었었던 풀이를 봤다.

애초에 graph를 탐색하면서 'W' 인지 'B'인지 구분 후 bfs(x,y,color) 의  매개변수로 color도 같이 넘기면 된다.

import sys
from collections import deque
input = sys.stdin.readline

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

N,M = map(int,input().split())
graph = [list(input().rstrip()) for _ in range(M)]

def bfs(x,y,color):
    q = deque()
    q.append((x,y))
    graph[x][y] = '.'
    cnt = 1

    while q:
        x_, y_ = q.popleft()

        for i in range(4):
            nx = x_ + dx[i]
            ny = y_ + dy[i]

            if (0 <= nx < N and 0 <= ny < M and graph[nx][ny] == color):
                q.append((nx,ny))
                graph[nx][ny] = '.'
                cnt += 1

    return cnt

W_result = 0
B_result = 0
for i in range(M):
    for j in range(N):
        if graph[i][j] == 'W':
            W_result += bfs(i,j,'W') **2
        elif graph[i][j] == 'B':
            B_result += bfs(i,j,'B') **2

print(W_result, B_result)