수학과의 개발자 도전기

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

처음에는 bfs로 진행했고, 1) 적군 지역을 모두 visit리스트에 입력한 뒤, 2) 하나의 적군지역을 기준으로 주어진 범위에 해당하는(r만큼) 통신지역을 모두 q에 넣는다. 

3) 다음 적군으로 이동했을 때(visit에서 popleft()) 해당 적군의 통신 지역이 q에 있다면 통신 지역이 겹치는 것이므로 cnt의 값을 하나씩 지워나가는 방식으로 갯수를 구하려고 했는데 시간초과가 발생해서 다른 방법을 찾아보았다.

참고한 블로그

-정답풀이: 

dfs() 식 풀이

1-1) distance(location[current],location[j]):

current번째 적군과 어떤 적군 사이의 거리

1-2) (location[current][2]+location[j][2]):

location[current][2]: current 적군의 통신 범위(반지름 길이)

location[j][2]: 어떤 적군의 통신 범위(반지름 길이)

2) cur==j:

자기 자신에 대해서 연산을 수행하는 경우

3) visit[j]:

이미 방문한 적군

===>위의 3가지 경우(통신 범위가 다른 적군의 통신 범위에 미치지 못하는 경우, 자기 자신인 경우, 이미 방문한 적군인 경우)에는 continue를 하고, 이 외의 상황에 대해서 방문 처리를 하고, 재귀를 수행한다 

import sys
input=sys.stdin.readline
def distance(a,b):
    return (a[0]-b[0])**2+(a[1]-b[1])**2

def dfs(current):
    for j in range(n):
        if distance(location[current],location[j])>(location[current][2]+location[j][2])**2 or current==j or visit[j]:
            continue
        visit[j]=True
        dfs(j)
        
t=int(input())
for _ in range(t):
    n=int(input())
    answer=0
    location=[]
    visit=[False for _ in range(n)]
    for _ in range(n):
        location.append(list(map(int,input().split())))
    for i in range(n):
        if not visit[i]:
            dfs(i)
            answer+=1
    print(answer)

-시간초과 풀이:

처음에 a,b,c in visit: 라고 실행했었는데, 이렇게 하니 Error가 발생해서 파이썬 튜터로 정확히 어떤 문제인지 찾아보니 

deque mutated during iteration 에러였다. 이거는 deque가 반복문을 돌리 때 deque의 내용이 변질되거나 사이즈가 변경될 때 뜨는 오류라고해서 visit를 deep copy한 result를 설정해서 돌려주었다. 그러더니 시간초과가 발생했다. 

from collections import deque
import copy
def bfs(x,y,r):
    global cnt
    flag=False
    q=deque()
    while visit:
        x,y,r=visit.popleft()
        for i in range(4):
            for j in range(1,r+1):
                a,b=x+j*dx[i],y+j*dy[i]
                if (a,b) not in q:
                    q.append((a,b))
                else:
                    flag=True
                    continue
        if flag:
            cnt-=1 #겹치는 구역 하나씩 빼기
            
t=int(input())
dx=[-1,1,0,0]
dy=[0,0,-1,1]
for _ in range(t):
    n=int(input())
    visit=deque()
    for _ in range(n):
        x,y,r=map(int,input().split())
        visit.append((x,y,r))
    result=copy.deepcopy(visit)    
    cnt=n
    for a,b,c in result:
        bfs(a,b,c)
    cnt=n
    print(cnt)

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

사이클 있는지 여부를 구하는 문제이다. 

이전에 사이클 관련 문제를 푼 적이 있기에 cycle이라는 리스트를 선언해서 이동할 때 방문하지 않았고, 사이클 문자와 동일한 경우만 cycle리스트에 삽입해준 후 이동하다 문자가 cycle에 있는 문자와 같을 경우 True를 선언하고 함수를 종료하는 거라고 생각했다. 생각해보니 cycle에는 이미 같은 문자들만 들어가있다;; 이부분 주의하기!!

그러니 문제에서 말한대로 처음 좌표와 들어온 값의 좌표가 같고, 크기가 4이상인 경우 사이클이라고 간주해 flag=True를 하고 반환하면 된다.

매 dfs를 실행할 때마다 visit 행렬을 초기화해준다 

-정답풀이: 

n,m=map(int,input().split())
s=[list(input()) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*m for _ in range(n)]

def dfs(x,y,word,cnt,sx,sy):    
    global flag   
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            #사이클 길이 4이상이면서, 첫번째 좌표가 현재 좌표가 같으면 True
            if cnt>=4 and sx==nx and sy==ny: ###
                flag=True
                return
            if not visit[nx][ny] and s[nx][ny]==word:
                visit[nx][ny]=1
                dfs(nx,ny,word,cnt+1,sx,sy)
                
flag=False
for i in range(n):
    for j in range(m):
        sx,sy=i,j
        visit=[[0]*m for _ in range(n)] ###
        visit[sx][sy]=1
        dfs(i,j,s[i][j],1,sx,sy)
        if flag:
            print("Yes")
            exit()
        
if not flag:
    print("No")

-틀린 풀이: 

메모리초과,RecursionError가 다 났던 코드,,

n,m=map(int,input().split())
s=[list(input()) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*m for _ in range(n)]

def dfs(x,y,word):
    visit[x][y]=1
    global flag
    cycle.append(s[x][y])
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if visit[nx][ny] and s[nx][ny]==word:
                if s[nx][ny] in cycle:
                    flag=True
                    return
            else:
                dfs(nx,ny,word)
flag=False
for i in range(n):
    for j in range(m):
        if not visit[i][j]:
            cycle=[]
            dfs(i,j,s[i][j])
            if flag:
                print("Yes")
                exit()
if not flag:
    print("No")

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

주어진 그래프를 가지고 자식 노드들을 정리해야지 해당 쿼리에 해당하는 자식노드들을 셀 수 있다고 생각했다. 그래서 먼저 

그래프를 만들고, 자식 노드 갯수를 세는 방식으로 했는데 시간초과가 발생했다. 

어차피 루트 노드가 주어지므로, 루트 노드를 중심으로 뻗어나가면 자연스럽게 한 노드에 대한 자식노드가 정리 되기 때문에 굳이 트리를 만들지 않아도 된다 

이후 트리에서 마지막 입력받는 정점을 루트로하는 서브트리의 정점의 수를 출력하면 된다

dfs로 탐색하면서 각 정점에 대한 서브트리의 수를 count 배열에 담아준다

count배열로 방문여부 표시도 같이 해줄 수 있다 

참고한 블로그

-정답풀이:

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline

N,R,Q=map(int,input().split())
graph=[[] for _ in range(N+1)]
size=[0]*(N+1)

for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def countPoint(x):
    size[x]=1
    for i in graph[x]:
        if not size[i]:
            countPoint(i)
            size[x]+=size[i]
countPoint(R)

for _ in range(Q):
    y=int(input())
    print(size[y])

-주의할점

graph=[[]*(N+1)]로 그래프를 초기화 했더니 IndexError가 발생했다. 찾아보니

이렇게 하면 graph=[[]]<- 이렇게 생겨서 값을 추가 할 수있는 인덱스가 없다. 

graph=[[] for _ in range(N+1)] 방식으로 작성하자!

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

풀이 없이 스스로 푼 문제. Silver Level1 문제이다. 탐색에는 특히 골드 문제가 많기 때문에 계속해서 탐색공부를 해야할 것 같다 

주의해야할 점이 세로가 m, 가로가 n이기 때문에 이것을 고려해서 풀어야한다

-정답풀이: 

처음에는 dfs로 풀었는데 틀려서 bfs로 바꿔서 풀고 맞힌 문제이다 

from collections import deque

def bfs(x,y,word):
    visit[x][y]=1
    cnt=1
    q=deque()
    q.append((x,y))
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<m and 0<=ny<n:
                if not visit[nx][ny] and s[nx][ny]==word:
                    visit[nx][ny]=1
                    cnt+=1
                    q.append((nx,ny))
    return cnt

n,m=map(int,input().split()) 
s=[list(input()) for _ in range(m)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*n for _ in range(m)]
white=0
blue=0

for i in range(m):
    for j in range(n):
        if not visit[i][j]:
            if s[i][j]=='W':
                ans=bfs(i,j,'W')
                white+=(ans**2)               
            elif s[i][j]=='B':
                ans=bfs(i,j,'B')
                blue+=(ans**2)
                
print(white,blue)