수학과의 개발자 도전기

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

문제 유형은 그동안 풀었던 유형인데, hxw 행렬인 거랑, 대각선으로 이동하는 것에서 헤맸던 문제다.

Silver Level2 문제!

-정답 풀이 :

from collections import deque
import sys
input=sys.stdin.readline

def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    while queue:
        x,y=queue.popleft()
        for i in range(8):
            nx,ny=x+direct[i][0],y+direct[i][1]            
            if 0<=nx<h and 0<=ny<w:
                if not visit[nx][ny] and data[nx][ny]==1:
                    visit[nx][ny]=1
                    queue.append((nx,ny))
while True:
    w,h=map(int,input().split())
    if w==0 and h==0:
        break
    data=[]
    for _ in range(h):
        data.append(list(map(int,input().split())))
    #방향 때문에 엄청 틀렸네,,,,
    direct=[[1,1],[-1,1],[1,-1],[-1,-1],[0,-1],[0,1],[1,0],[-1,0]]
    count=0
    visit=[[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if not visit[i][j] and data[i][j]==1:
                visit[i][j]=1
                count+=1
                bfs(i,j)
                
    print(count)

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

이번이 세번째 풀이인데도 막히는 부분이 똑같아서 이번에는 세밀하게 코드를 분석해보려고 한다 

참고로 pypy3으로 돌려야 시간초과가 안 발생한다 

로직 

1. 벽(1) 3개를 설치하기 

2. 벽 설치가 완료되면 2인 지점을 찾아서 바이러스 전파 -> bfs()를 통해 구현

3. 바이러스 전파 완료되면 0의 갯수 셈 -> get_num()을 통해 구현 

순서

-벽 설치 완료? 

if count ==3:

data 복사

for i in range(n):
	for j in range(m):
    	temp[i][j]=data[i][j]

2인 지점찾고, 바이러스 전파 

for i in range(n):
	for j in range(m):
    	if temp[i][j]==2:
        	bfs(i,j)

전파 완료되면 0의 갯수 세기

answer=max(answer,get_num())

def get_num():
	num=0
    for i in range(n):
    	for j in range(m):
        	if temp[i][j]==0:
            	num+=1
	return num

-완료가 안됐으면, 벽 세우기 

for i in range(n):
	for j in range(m):
    	if data[i][j]==0:
        	data[i][j]=1
            count+=1
            dfs(count)
            #다른 경우도 진행해야하므로 값 초기화 
            data[i][j]=0
            count-=1

- 정답 풀이 :

from collections import deque

n,m=map(int,input().split())
data=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
answer=0
temp=[[0]*m for _ in range(n)]

for i in range(n):
    data.append(list(map(int,input().split())))

def bfs(x,y):
    queue=deque()
    queue.append((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<m:
                #data가 아닌 temp임!
                if temp[nx][ny]==0:
                    temp[nx][ny]=2
                    queue.append((nx,ny))

def get_num():
    num=0
    for i in range(n):
        for j in range(m):
            #data가 아닌 temp임!
            if temp[i][j]==0:
                num+=1
    return num 

def dfs(count):
    global answer
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j]=data[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j]==2:
                    bfs(i,j)
        answer=max(answer,get_num()) 
        return 
    for i in range(n):
        for j in range(m):
            if data[i][j]==0:
                data[i][j]=1
                count+=1
                dfs(count)
                data[i][j]=0
                count-=1

dfs(0)
print(answer)

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

스스로 푼 문제다! Silver Level2 문제 

찾아보니까 연결요소가 간선으로 연결된 노드의 집합인 것 같다. 

공통 요소가 없는 노드는 연결요소가 아니라고 이해했다. 

그래서 하나의 연결요소를 진행하면 연결요소의 노드들은 모두 visit처리가 된다. 

하지만 이 연결요소의 원소가 아닌 노드들은 visit처리가 되지 않았으므로, 이를 이용해서 다시 dfs를 진행하면 된다. 

새로운 연결요소가 추가된 것이므로, count+=1 해준 후 마지막에 출력했다 

밑의 풀이는 python3로도 돌아가는데, 

여기를 빼고 

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

pypy3으로 돌려도 정답이 뜬다. 코테 시험장에서 pypy3가 없는 곳을 대비해서 import sys 파트도 연습해봤다

-정답 풀이 :

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

n,m=map(int,input().split())
data=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
    data[a].sort()
    data[b].sort()
   

def dfs(v):
    visit[v]=1
    for i in data[v]:
        if not visit[i]:
            visit[i]=1
            dfs(i)
            
count=0  
visit=[0]*(n+1) 
for i in range(1,n+1):
    if not visit[i]:
        count+=1
        dfs(i)
        
print(count)

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

스스로 푼 문제다. Silver Level 3 문제 

첫번째 탐색문제에서 dfs 푸는 방식이 동일했다. 지나온 원소들을 세면 되어서 sum(visit)를 했는데, 1을 제외하라고 해서 

마지막에 -1을 해주었다 

- 정답 풀이 :

n=int(input())
m=int(input())
data=[[] for _ in range(n+1)]

for _ in range(m):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
    data[a].sort()
    data[b].sort()
    
visit=[0]*(n+1)

def dfs(v):
    for i in data[v]:
        if not visit[i]:
            visit[i]=1
            dfs(i)
            
dfs(1)
print(sum(visit)-1)