수학과의 개발자 도전기

-문제: https://www.acmicpc.net/problem/11724

쉬운데 괜히 어렵게 생각했던 문제.

기본 bfs를 구현한 다음에 bfs가 실행될 때마다 연결요소 개수가 증가한다고 생각하면 된다

만약 연결요소가 하나라면 bfs가 한번 실행된 후 모두 visited가 True일 것이므로 not visited가 더이상 발생하지 않아 bfs가 더는 실행되지 않고, cnt는 1이 된다 

-정답풀이: 

from collections import deque

def bfs(graph,v,visited):
    queue=deque()
    queue.append(v)
    visited[v]=True
    while queue:
        x=queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                visited[i]=True
                queue.append(i)
                
n,m=map(int,input().split())
graph=[[] for _ in range(n+1)]
visited=[False]*(n+1)

for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
cnt=0
for i in range(1,n+1):
    if not visited[i]:
        bfs(graph,i,visited)
        cnt+=1
print(cnt)

-문제: https://www.acmicpc.net/problem/2606

dfs로 풀고 싶어서 dfs로 풀었는데 전역번수 cnt 위치를 잘못 지정해서 틀렸던 문제다

-정답풀이: 

def dfs(s,v,visited):
    global cnt
    visited[v]=True    
    for i in s[v]:
        if not visited[i]:
            cnt+=1
            dfs(s,i,visited)

n=int(input())
con=int(input())
s=[[] for _ in range(n+1)]
visited=[False]*(n+1)
cnt=0
for _ in range(con):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
    s[a].sort()
    s[b].sort()
    
dfs(s,1,visited)
print(cnt)

-틀린풀이: 

밑의 4번 라인에 있는 cnt+=1을 if not visited[i]: 다음으로 넘겼더니 바로 정답이 나왔다

1번과 연결되어 있는 것 중에 방문한 것들을 모두 세야하므로 for문 안에 cnt+=1를 넣어줘야한다

-문제: https://www.acmicpc.net/problem/2667

-풀이 이해:

dfs가 생각이 나서 dfs로 풀려고 했는데, 전체 갯수는 세는 건 알고 있는데 

각 단지에 해당하는 단지수를 어떻게 풀어야할지 몰랐다. 

dfs에서 True,False 반환하는 거 말고, 1을 만날때마다 cnt를 세고 싶은데 어떻게 해야할지 몰랐다.

찾아보니 global 키워드를 이용하면 된다는 걸 알았다 

-정답풀이:

단지가 완성이 되면, cnt값을 리스트에 삽입하고 다시 cnt를 0으로 초기화한다

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

for _ in range(n):
    s.append(list(map(int,input())))
    
def dfs(x,y):
    if x<0 or y<0 or x>=n or y>=n:
        return False
    if s[x][y]==1:
        global cnt 
        s[x][y]=0
        cnt+=1
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False

result=0
cnt=0
apartment=[]
for i in range(n):
    for j in range(n):
        if dfs(i,j)==True:
            apartment.append(cnt)
            result+=1
            cnt=0          
print(result)
apartment.sort()  
for i in range(result):
    print(apartment[i])