수학과의 개발자 도전기

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

bfs로 풀려고 했다가

저번에 풀었던 아이스크림 갯수 구하는 거랑 문제가 비슷하길래 dfs로 풀어보려고 했는데 틀렸던 문제다 

-DFS 풀이

sys.setrecursionlimit없이 돌렸더니 RecursionError가 발생했다. dfs에서는 recursionlimit 달아주자!

스스로 짠 dfs 코드와 다른 점은 내 풀이는 dfs 실행하면 처음 받은 x,y를 기준으로 경곗값을 판단했는데, 정답풀이에서는 x,y를 이동한 nx,ny를 기준으로 경곗값 확인 후 dfs를 진행했다 

22번 라인에서 전체 행렬 탐색 중에 1인 값 만나면 거기서부터 섬의 영역 확인하는 방식으로 가야한다 

import sys
sys.setrecursionlimit(10000)

directions=[[1,1],[1,-1],[1,0],[-1,0],[-1,1],[0,-1],[-1,-1],[0,1]]
def dfs(x,y):
    s[x][y]=0
    for i in range(8):
        nx,ny=x+directions[i][0],y+directions[i][1]
        if 0<=nx<h and 0<=ny<w and s[nx][ny]==1:
            dfs(nx,ny)
                                            
while True:
    w,h= map(int,input().split())
    s=[]
    if w==0 and h==0:
        break
    for _ in range(h):
        s.append(list(map(int,input().split())))
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]==1:
                dfs(i,j)
                ans+=1
    print(ans)

-내가 작성한 DFS 풀이

setrecursionlimit 없고 3번 라인, 21번 라인이 정답 풀이와 다르다

-BFS 풀이 

from collections import deque

def bfs(x,y):
    directions=[[1,1],[1,-1],[1,0],[-1,0],[-1,1],[0,-1],[-1,-1],[0,1]]
    s[x][y]=0
    queue=deque()
    queue.append([x,y])
    while queue:
        x,y=queue[0][0],queue[0][1]
        queue.popleft()
        for i in range(8):
            nx,ny= x+directions[i][0],y+directions[i][1]
            if 0<=nx<h and 0<=ny<w :
                if s[nx][ny]==1:
                    s[nx][ny]=0
                    queue.append([nx,ny])
                    
while True:
    w,h= map(int,input().split())
    s=[]
    ans=0
    if w==0 and h==0:
        break
    for _ in range(h):
        s.append(list(map(int,input().split())))
    for i in range(h):
        for j in range(w):
            if s[i][j]==1:
                bfs(i,j)
                ans+=1
    print(ans)

-내가 작성한 BFS 풀이 

비슷하긴 한데 아직 부족한 부분이 좀 있다. 더 공부하자!

그래도 종료 조건에 while True: if문 사용한 거랑, 

대각선으로 이동하는 거 direction 리스트 구현한 거, 

bfs()함수 맞게 구현한 것만 해도 많이 발전했다!!

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

어려웠던 문제.

아이디어는 생각났는데, 그걸 코드로 옮기는 걸 몰랐다.

아이디어는

1.  조건에 맞추어 벽을 세개 세우기

2. 2주변 다 2로 바꾸기

3. 0의 갯수 출력

2,3은 bfs이용하면 될 것 같은데 1번을 어떻게 해야할지 잘 몰랐다.

select_wall을 참고하면 된다

-정답풀이: 

기본 정보 받는 코드. 여기까지는 오케이 

copy.deepcopy()는 깊은 복사로, 내부의 객체들까지 모두 새롭게 copy되는 것이다. 

nm에 변화가 생겨도 sel_nm은 복사한 상태 그대로 유지된다 

벽을 3개 모두 세웠을 때와 그 전인 경우로 나뉜다.

먼저 벽을 3개 모두 세웠을 때를 보면

깊은 복사한 것을 기준으로 바이러스를 전파시키고, 전파가 끝나면 

전체 0의 갯수를 센다 

벽이 3개 미만으로 세워졌을 때는 else문을 참고하면 되는데 

이 다음이 이해가 가지 않는다 

여기도 오케이. bfs

-문제: 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를 넣어줘야한다