[CLASS 3]백준 11724번, 1389번, 1697번, 2178번, 2667번

11724번 : 연결 요소의 개수

 

어... 그냥 그래프 탐색 문제이다. dfs혹은 bfs중 어떤 것으로 풀든 상관 없다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
from collections import deque

input = stdin.readline

n,m = map(int,input().split())

# 정점 저장
nodes = [[] for _ in range(n+1)]
# 방문 처리
visited = [False] * (n+1)
for _ in range(m):
    i,j = map(int,input().split())
    nodes[i].append(j)
    nodes[j].append(i)

# 너비 우선 탐색
def bfs(start):
    global nodes,visited
    if visited[start]:
        return 0

    visited[start] = True
    queue = deque([start])

    while queue:
        for node in nodes[queue.popleft()]:
            if not visited[node]:
                visited[node] = True
                queue.append(node)

    return 1

# 깊이 우선 탐색
def dfs(start):
    global nodes,visited
    if visited[start]:
        return 0
    
    visited[start] = True
    stack = [start]

    if not nodes[stack[-1]]:
        return 1
    while stack:
        for idx,node in enumerate(nodes[stack[-1]]):
            if not visited[node]:
                visited[node] = True
                stack.append(node)
                break
            if idx == len(nodes[stack[-1]]) - 1:
                stack.pop()
    
    return 1

count = 0
for i in range(1,n+1):
    count += dfs(i)
print(count)

 

항상 생각하지만 dfs를 사용할때 재귀함수가 아닌 스택으로 구현했다면 코드는 bfs가 더 간단하고 명료한 것 같다. 내 실력 부족일 수 있겠지만 스택을 사용해서 깊이 우선 탐색도 좀 깔끔하게 작성해보고 싶다.

 

1389번 : 케빈 베이컨의 6단계 법칙

 

신기한 법칙에 대한 설명이 나와 있고 문제가 쓰여 있다. 문제는 단순히 그래프 탐색을 통해 풀이가 가능하다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
from collections import deque

n, m = map(int,input().split())

# 사람들 연결관계를 저장하는 리스트
people = [set() for _ in range(n+1)]
for _ in range(m):
    i,j = map(int,input().split())
    people[i].add(j)
    people[j].add(i)

# 너비 우선 탐색
def find(p):
    counted = [0] * (n+1)
    queue = deque([p])
    while queue:
        this = queue.popleft()
        for person in people[this]:
            if not counted[person]:
                counted[person] = counted[this] + 1
                queue.append(person)
    
    return sum(counted) - counted[p]

minStep = 1e9
minPerson = None
# 모든 사람 단계 검사
for i in range(1,n+1):
    step = find(i)
    if step < minStep:
        minStep = step
        minPerson = i

# 최소 단계를 가진 사람 출력
print(minPerson)

 

모든 사람에 대해 너비 우선 탐색을 진행하면 된다. 그러면 다른 모든 사람에 대한 케빈 베이컨 수가 나오고, 이를 합한 값이 가장 작은 사람의 번호를 출력하면 된다.

 

1697번 : 숨바꼭질

 

솔직히 처음 보고 DP로 푸는 건줄 알았다. 그 뒤 DP로 열심히 작성했지만... 성공하지 못했다.

 

그래서 도대체 어떻게 푸는 것인가 고민하다가 문제 분류를 봤는데 너비 우선 탐색(BFS)였다... 그래서 바로 코드를 작성했다.

 

내 코드:

# dawitblog.tistory.com
from collections import deque

n, k = map(int,input().split())
if k <= n:
    print(n-k)
    exit()

nodes = [[i-1,i+1,2*i] for i in range(2*k)]
visited = [False] * 2 * (k+1)
queue = deque([n])
visited[n] = True
count, addedCount, temp = 1,1,0
while queue:
    addedCount -= 1
    for near in nodes[queue.popleft()]:
        if near == k:
            print(count)
            exit()
        if near <= 2*(k-1) and not visited[near]:
            visited[near] = True
            queue.append(near)
            temp += 1

    if addedCount == 0:
        addedCount = temp
        temp = 0
        count += 1

해당 코드에서 temp와 addedCount는 해당 단계에서 몇개가 추가되었는지를 세는 변수이다. 예를 들어 처음에 큐에 5가 있었다면, 4,6,10이 큐에 추가될것이다. 이때 addedCount는 3이 된다. 그리고 큐에서 addedCount만큼의 탐색을 한  뒤(즉 4,6,10을 모두 탐색한 뒤)에 addedCount를 7로 갱신한다(3,8,7,12,9,11,20).

 

 

솔직히 너비 우선 탐색을 이 문제에 적용할 생각을 못했다. 그걸 먼저 알고 있었다면 훨씬 빠르고 쉽게 풀 수 있었을 것이다.

 

res1235님의 코드:

def c(n,k):
    if n>=k:
        return n-k
    elif k == 1:
        return 1
    elif k%2:
        return 1+min(c(n,k-1),c(n,k+1))
    else:
        return min(k-n, 1+c(n,k//2))
    
n, k = map(int,input().split())
print(c(n,k))

 

dp는 아니지만 재귀함수로 작성한 코드이다.

 

2178번 : 미로 탐색

 

보자마자 DFS가 생각나서 그 방법으로 풀었지만 DFS로 풀기는 좀 힘든 것 같다. 왜냐하면 DFS로 풀게 되면 스택에 집어넣을때 아래 혹은 오른쪽을 무조건 먼저 검사하고 먼저 넣게 된다. 이렇게 되면 

 

1	1	0	1	1	0
1	1	0	1	1	0
1	1	1	1	1	1
1	1	1	1	0	1

 

이런 미로가 문제가 된다. 만약 DFS로 코드를 작성할 때 인접한 길 중 아래로 갈 수 있다면 아래로 가고 스택에 집어넣는 연산을 계속 하다 보면 왼쪽 하단에 도착하게 된다. 이후 아래로는 갈 수 없으므로 오른쪽으로 가게 된다면 3번을 오른쪽으로 더 간 뒤 벽에 막히게 된다. 이후 위->오른쪽->오른쪽->아래 를 통해 목적지에 도착하게 되는데, 이러면 쓸데없는 움직임이 2회 포함되어 버린다. 그래서 답이 잘못 나오게 된다.

 

그래서 BFS로 작성하는것이 더 편하겠다 생각하고 BFS로 작성했다.

 

내 코드:

# dawitblog.tistory.com
from collections import deque
n, m = map(int,input().split())
# 미로 list
maze = [[]] + [[0] + list(map(int,list(input()))) for _ in range(n)]
case = []

visited = [[]] + [[False] * (m+1) for _ in range(n)]

visited[1][1] = True
queue = deque([(1,1,1)])
while queue:
    tr,tc,d = queue.popleft()
    if tr + 1 <= n and maze[tr+1][tc] and visited[tr+1][tc] is False:
        visited[tr+1][tc] = True
        # 우측 하단에 도착하게 되면 바로 종료
        if (tr+1,tc) == (n,m):
            print(d+1)
            exit()
        queue.append((tr+1,tc,d+1))
    if tc + 1 <= m and maze[tr][tc+1] and visited[tr][tc+1] is False:
        visited[tr][tc+1] = True
        # 우측 하단에 도착하게 되면 바로 종료
        if (tr,tc+1) == (n,m):
            print(d+1)
            exit()
        queue.append((tr,tc+1,d+1))
    if tr - 1 > 0 and maze[tr-1][tc] and visited[tr-1][tc] is False:
        visited[tr-1][tc] = True
        queue.append((tr-1,tc,d+1))
    if tc - 1 > 0 and maze[tr][tc-1] and visited[tr][tc-1] is False: 
        visited[tr][tc-1] = True
        queue.append((tr,tc-1,d+1))

 

BFS로 작성하면 아까와 같은 문제는 발생하지 않는다. 한 노드가 방문 가능하면 그곳으로 계속 파고드는 DFS에 비해 BFS는 인접 노드들 중 방문 가능한 노드를 큐에 한꺼번에 올려놓고 탐색하기 때문이다. 문제를 풀 때 해당 문제가 그래프 탐색인지, DP인지, 그래프 탐색이라면 너비 우선으로 푸는게 좋을지 아니면 깊이 우선으로 푸는게 좋을지, 등을 먼저 생각해보고 문제에 접근하는게 좋은 습관인 것 같다. 이 문제 같은 경우 나는 그래프 탐색이라는 건 알았지만 BFS가 더 편하다는 생각은 훨씬 나중에 알게 된 점이 좀 아쉬웠다.

 

2667번 : 단지 번호붙이기

 

문제는 별로 어렵지 않다. 오름차순으로 출력하는것만 안까먹으면 될 것 같다.

 

이런 영역 구별 문제는 DFS로 푸나 BFS로 푸나 별 차이가 없는 것 같다. 그래서 나는 내가 좀 더 작성하기 편한 BFS로 작성했다.

 

내 코드:

# dawitblog.tistory.com
import sys
from collections import deque
input = sys.stdin.readline

# 지도 list
m = [list(map(int,list(input().rstrip()))) for _ in range(int(input()))]


# 너비 우선 탐색
def bfs(m,r,c):
    dr = [-1,1,0,0]
    dc = [0,0,-1,1]

    m[r][c] = 0
    queue = deque([(r,c)])
    count = 1

    while queue:
        tr,tc = queue.popleft()
        for i in range(4):
            newR = tr + dr[i]
            newC = tc + dc[i]
            if 0 <= newR < len(m) and 0 <= newC < len(m) and m[newR][newC]:
                m[newR][newC] = 0
                queue.append((newR,newC))
                count += 1
    
    return count

# 아파트 단지 수
aparts = 0
houses = []
for r in range(len(m)):
    for c in range(len(m)):
        if m[r][c]:
            aparts += 1
            houses.append(bfs(m,r,c))

print(aparts)
# 정렬 잊지말자.
print('\n'.join(map(str,sorted(houses))))

 

너비 우선 탐색으로 풀었다. 지도를 받아올 때 1과 0으로 되어있으므로 int 로 바꾸면 True 와 False로 판단할 수 있기 때문에 굳이 visisted list를 만들지 않아도 된다.