백준(1260,2178)

그래프 탐색(너비 우선 탐색)

DFS와BFS(1260)

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

• 입력

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

• 입출력 예시

4 5 1
1 2
1 3
1 4
2 4
3 4

------------

1 2 4 3
1 2 3 4

• 해결책
  1. 그래프탐색을 구현할 수 있는지 묻고 있는 문제이다.
  1. DFS→ 재귀함수를 이용해 쉽게 구현할 수 있다.
  2. BFS → 리스트나 deque을 이용해 queue를 생성하고 append, popleft해주면된다.
     1. DFS에서 BFS탐색으로 넘어갈때 방문배열을 초기화해야하는 것을 잊지말자.

코드

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

def dfs(s,maps,depth):
    if visited[s]:
        return
    else :

        print(s,end=' ')
        visited[s]=1
       
        
        for i in maps[s]:
            if not visited[i]:
                
                dfs(i,maps,depth+1)
            
        
def bfs(s,maps):
    quu=deque([])
    quu.append(s)
    visited[s]=1
    while quu:
        work=quu.popleft()
        print(work,end=' ')
        for i in maps[work]:
            if  not visited[i]:
                visited[i]=1
                quu.append(i)
            
        
        

n,m,s=map(int,input().split())
maps={}
path=[]
visited=[0]*(n+1)
for i in range(n):
    maps[i+1]=[]

for i in range(m):
    start,end = map(int,input().split())
    maps[start].append(end)
    maps[end].append(start)

for i in range(n):
    maps[i+1]=sorted(maps[i+1]) # 문제조건의 오름차순 방문 기준에 따라 각리스트 정렬

dfs(s,maps,1) #깊이
visited=[0]*(n+1) # 방문배열 초기화!
print()

bfs(s,maps) #너비

미로찾기(2178)

N×M크기의 배열로 표현되는 미로가 있다.

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

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

• 입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

• 입출력 예시

4 6
101111
101010
101011
111011

------------

15

• 해결책

🔑 이문제는 입력부터 신경써야한다. 공백 구분자가 아닌 string이므로, string을 int 리스트로 변환한뒤 map리스트에 append시켜줘야한다.

1. 문제자체는 4방향 queue(bfs)를 이용하면 쉽게 구현할 수 있다.
2. 4방향에 맞게 (1,0),(-1,0),(0,1),(0,-1)를 append하는 조건으로 지정해준다.
   1. bfs는 append할때 visited배열을 체킹해준다는 것을 잊지말자.

코드

from collections import deque
import sys
input = sys.stdin.readline
def bfs(start,maps):
    q=deque([])
    q.append((0,0,start))
    visit[0][0]=1
    dx=[1,0,-1,0] 
    dy=[0,1,0,-1]
    while q:
        node=q.popleft()
        for i in range(4):
            
            nx = node[0]+dx[i]
            ny = node[1]+dy[i]
            value = node[2]+1
            
            if nx>=0 and nx<n and ny>=0 and ny<m :
                if not visit[nx][ny] and maps[nx][ny]:
                    visit[nx][ny]=1
                    maps[nx][ny]=value
                    q.append((nx,ny,value))
    print(maps[n-1][m-1]) # 도착지는 고정이므로, maps에 삽입해준 값을 출력만해주면된다.
    
    

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

for i in range(n):
    visit.append([0]*m)

bfs(1,graph)