수학과의 개발자 도전기

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

쉬운 문제인데 적록색약 입장에서 갯수세는데 필요한 아이디어가 생각이 안났다.

bfs로 진행하고, i,j 위치에있는 문자값과 같은 것을 기준으로 진행하면 된다고 생각했지만

'R'을 'G'로 바꾸어서 적록색약 진행하는 거랑 map(str~)이 부분을 잘 하지 못했다

for _ in range(n):
    s.append(list(map(str,input())))

for i in range(n):
    for j in range(n):
        if s[i][j]=='G':
            s[i][j]='R'

-정답풀이:

from collections import deque
n=int(input())
s=[]
for _ in range(n):
    s.append(list(map(str,input())))
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*(n+1) for _ in range(n+1)]

def bfs(x,y):
    queue=deque()
    queue.append([x,y])
    word=s[x][y]
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<n and s[nx][ny]==word and visit[nx][ny]==0:
                queue.append([nx,ny])
                visit[nx][ny]=1
ans=0
for i in range(n):
    for j in range(n):
        if not visit[i][j]:
            bfs(i,j)
            ans+=1
print(ans,end=' ')

for i in range(n):
    for j in range(n):
        if s[i][j]=='G':
            s[i][j]='R'
visit=[[0]*(n+1) for _ in range(n+1)] 
ans=0
for i in range(n):
    for j in range(n):
        if not visit[i][j]:
            bfs(i,j)
            ans+=1
print(ans)

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

이전에 푼거에 z가 추가된 형태.

근데도 답을 찾아봤고 답을 옮기는데도 어려움이 있었던 문제 

-정답풀이: 

from collections import deque

m,n,h=map(int,input().split())
s=[[] for _ in range(h)]
for i in range(h):
    for j in range(n):
        s[i].append(list(map(int,input().split())))

dx=[-1,1,0,0,0,0]
dy=[0,0,-1,1,0,0]
dz=[0,0,0,0,-1,1]

def bfs():
    while queue:
        z,x,y=queue.popleft()
        for i in range(6):
            nx=x+dx[i]
            ny=y+dy[i]
            nz=z+dz[i]
            if 0<=nx<n and 0<=ny<m and 0<=nz<h and s[nz][nx][ny]==0 :
                s[nz][nx][ny]=s[z][x][y]+1
                queue.append([nz,nx,ny])
                
queue=deque()
for z in range(h):
    for x in range(n):
        for y in range(m):
            if s[z][x][y]==1:
                queue.append([z,x,y])

bfs()
k=1
result= -1
for z in s:
    for y in z:
        for x in y:
            if x==0:
                k=0
            result=max(result,x)
            
if k==0:
    print(-1)
else:
    print(result-1)

-문제: 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