dfs,bfs-(1)

 

문제 1. 특정거리의 도시찾기

18352번: 특정 거리의 도시 찾기

1. 메모리초과

=> 코드를 작성할때 이차원 list의 크기를 n+1*n+1로 하였기 때문에 메모리초과가 나게 됨.

from collections import deque
import sys

input = sys.stdin.readline

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

map_list = []
for i in range(0,m):
    NODE = list(map(int, input().split()))
    if  NODE[0]!=NODE[1]:
        map_list.append(NODE)

k_list=[0]*(n+1)

visit=[]
start=x
queue_node = deque()
queue_cnt = deque()

cnt=0
queue_node.append(start)
queue_cnt.append(cnt)

while True:
    if len(queue_cnt)==0:
        break
    cnt = queue_cnt.popleft()
    node = queue_node.popleft()
    
    if cnt>k:
        break

    if cnt<=k:
        if k_list[node] ==0:
            k_list[node]= cnt
        else:
            k_list[node]=min(k_list[node],cnt)


    for i in range(0,m):
        if node == map_list[i][0] and not map_list[i][0] in visit:
            queue_node.append(map_list[i][1])
            queue_cnt.append(cnt+1)
    visit.append(node)       
#print(k_list)

if not k in k_list:
    print("-1")

for i in range(1,n+1):
    if k==k_list[i]:
        print(i)

 

=>=> visit을 구현하지 않아서 이미 갔던 노드를 또 방문할 수 있기에 시간초과가 뜬 것 같아서 구현했지만 여전히 시간초과 문제가 발생

=> test case 3개의 결과는 모두 같게 나오지만 8%까지 진행하다가 시간초과가 나오게 됨.

=> 스터디를 통해서 해결해볼예정

 

 

---

문제 2. 연구실

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

14502번: 연구소

 

#연구실 => 바이러스가 아닌 공간이 최대가 하도록 3개의 벽을 세우는 문제


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

map_list=[]
#visit=[0]*n

for i in range(0,n):
    list_ = list(map(int,input().split()))
    map_list.append(list_)
    #visit.append([0]*m)


list_2=[]
for i in range(0,n):
    for j in range(0,m):
        if map_list[i][j]==2:
            list_=[i,j]
            list_2.append(list_)
            


def dfs(x,y):
    if x-1>=0 and map_list[x-1][y]==0:
        map_list[x-1][y]=2
        dfs(x-1, y)
    if x+1<n and map_list[x+1][y]==0:
        map_list[x+1][y]=2
        dfs(x+1,y)
    if y-1>=0 and map_list[x][y-1]==0:
        map_list[x][y-1]=2
        dfs(x,y-1)
    if y+1<m and map_list[x][y+1]==0:
        map_list[x][y+1]=2
        dfs(x,y+1)

import copy
cnt_list=[]
map2 = copy.deepcopy(map_list)

for i in range(0, n):
    for j in range(0,m):
        for i2 in range(0,n):
            for j2 in range(0, m):
                    for i3 in range(0,n):
                        for j3 in range(0,m):
                            if not((i2==i3 and j2==j3) or(i3==i and j3==j) or (i==i2 and j==j2)):
                               # if i==0 and j==3 and i2==4 and j2==1 and i3==3 and j3==4:
                                    #print(map_list[i][j],map_list[i2][j2],map_list[i3][j3])
                                    if map_list[i][j]==0 and map_list[i2][j2]==0 and map_list[i3][j3]==0:
                                        map_list[i][j]=1
                                        map_list[i2][j2]=1
                                        map_list[i3][j3]=1
                                        for a in list_2:
                                            dfs(a[0],a[1])
                                            #print(map_list)
                                        cnt=0
                                        for h in range(0,n):
                                            cnt+=map_list[h].count(0)
                                        #print(cnt)
                                        cnt_list.append(cnt)
                                        map_list = copy.deepcopy(map2)
                                

print(max(cnt_list))

=> 예제 testcase에 있는 값들에 대한 정답은 모두 일치하지만 시간초과 발생 => 생각해본 해결방법 :  for문 6개를 사용하지 않고 0이있는 좌표 3개를 고르도록 해야할 것 같음. 

=> from itertools import combinations를 사용하는 것도 좋을 것 같음 =>https://ourcstory.tistory.com/414 참고 예정

 

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

map_list = []
# visit=[0]*n

for i in range(0, n):
    list_ = list(map(int, input().split()))
    map_list.append(list_)
    # visit.append([0]*m)


list_2 = []
for i in range(0, n):
    for j in range(0, m):
        if map_list[i][j] == 2:
            list_2.append([i, j])


def dfs(x, y):
    if x - 1 >= 0 and map_list[x - 1][y] == 0:
        map_list[x - 1][y] = 2
        dfs(x - 1, y)
    if x + 1 < n and map_list[x + 1][y] == 0:
        map_list[x + 1][y] = 2
        dfs(x + 1, y)
    if y - 1 >= 0 and map_list[x][y - 1] == 0:
        map_list[x][y - 1] = 2
        dfs(x, y - 1)
    if y + 1 < m and map_list[x][y + 1] == 0:
        map_list[x][y + 1] = 2
        dfs(x, y + 1)


import copy

map2 = copy.deepcopy(map_list)

list_0 = []
for i in range(0, n):
    for j in range(0, m):
        if map_list[i][j] == 0:
            list_0.append([i, j])

from itertools import combinations

result = list(combinations(list_0, 3))

cnt_list = []

for i in range(0, len(result)):
    a, b, c = map(list, result[i])

    map_list[a[0]][a[1]] = 1
    map_list[b[0]][b[1]] = 1
    map_list[c[0]][c[1]] = 1

    for j in list_2:
        dfs(j[0], j[1])

    # for i1 in range(0, n):
    #     for j1 in range(0, m):
    #         print(map_list[i1][j1], end="")
    #     print()
    # print()
    cnt = 0
    for h in range(0, n):
        cnt += map_list[h].count(0)
    cnt_list.append(cnt)
    map_list = copy.deepcopy(map2)


print(max(cnt_list))

combination을 사용해 코드의 효율을 높인 결과 성공할 수 있었음.

---

3. dfs와 bfs 기본 예제

=> 양방향 연결된 노드를 가지고 dfs와 bfs 코드를 작성해보기

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

1260번: DFS와 BFS

#백준 1260

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

map_list=[]
visit = [0]*(n+1)

for i in range(0,m):
    a,b = map(int, input().split())
    list2=[a,b]
    list2_=[b,a]
    map_list.append(list2)
    map_list.append(list2_)

map_list.sort(key = lambda x:x[1])
map_list.sort(key = lambda x:x[0])


def dfs(start):
    print(start,end =' ')
    for i in range(0,len(map_list)):
        if map_list[i][0]==start and visit[map_list[i][1]]!=1:
            visit[map_list[i][1]]=1
            dfs(map_list[i][1])

visit[v]=1   
dfs(v)
visit = [0]*(n+1)

print()
from collections import deque

queue = deque()

def bfs(start):   
    while len(queue):
        node = queue.popleft()
        print(node,end=' ')
        for i in range(0,len(map_list)):
            if node==map_list[i][0] and visit[map_list[i][1]]!=1:
                visit[map_list[i][1]]=1
                queue.append(map_list[i][1])

visit[v]=1
queue.append(v)
bfs(v)

=> data들을 먼저 정렬한 후에 사용해야함