수학과의 개발자 도전기

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

채점까지 오래걸렸던 문제.

스스로 풀이 없이 푼 문제다 

처음에 dfs로 풀다가 setrecursionlimit(100000)까지 걸었는데 70몇퍼에서 recursionerror가 발생했다

그래서 bfs로 바꿨더니 맞은 문제

silver level2 문제 

-정답풀이:

from collections import deque

n=int(input())
graph=[[] for _ in range(n+1)]
ans=[0]*(n+1)

#그래프 정리 
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
visit=[0]*(n+1)    

def bfs(v):
    queue=deque()
    queue.append(v)
    visit[v]=1
    while queue:
        x=queue.popleft()
        for i in graph[x]:
            if not visit[i]:
                visit[i]=1
                queue.append(i)
                ans[i]=x
                
bfs(1)            
for i in range(2,n+1):
    print(ans[i])

-RecursionError 발생

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

2776번, 단지 붙이기와 같은 유형의 문제다

bfs문제로 풀기 어렵지 않은 문제다

스스로 푼 문제. silver level1이다 

문제에서 갯수와 각각의 빈공간의 갯수 출력하는 건데 잘 안보고 풀었더니 초반에 몇번 틀렸다.

문제 자세히 보는 건 기본!!

-주의 해야할 부분: 

1. bfs를 보면 ans=0에서 시작하기 때문에 처음 시작하는 한 칸의 갯수를 덜 센다

그래서 각각의 결과에 1을 더해줘야한다. 이거 때문에 마지막에 꽤 시간을 소요했다

2. 주어진 순서대로 행,열이라고 생각했는데 주어진 위치와 테이블 인덱스는 반대이므로 a,b,c,d로 받고

(b,a),(d,c) 순서로 생각하고 직사각형을 채워야한다 

-정답풀이: 

from collections import deque
m,n,k=map(int,input().split())
graph=[[0]*n for _ in range(m)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
#사각형 있는 곳 채우기(b,a)~(d,c)
for _ in range(k):
    a,b,c,d=map(int,input().split())
    for i in range(b,d):
        for j in range(a,c):
            graph[i][j]=1
            
def bfs(x,y):
    global ans
    queue=deque()
    queue.append([x,y])
    graph[x][y]=1
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<m and 0<=ny<n:
                if graph[nx][ny]==0:
                    graph[nx][ny]=1
                    queue.append([nx,ny])
                    ans+=1
ans=0
cnt=0
result=[]
for i in range(m):
    for j in range(n):
        if graph[i][j]==0:
            bfs(i,j)
            cnt+=1
            result.append(ans)
            ans=0
print(cnt)
result.sort()
for i in range(cnt):
    print(result[i]+1,end=' ')

-틀린풀이: 

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