둔필승총

www.acmicpc.net/problem/1012

[문제 풀이]

문제가 길지만 정리하자면 배추밭에서 1이 있는곳은 배추가 있는곳, 0은 배추가 없는 곳이다. 1이 있는 곳을 DFS해서 주위에 0으로 둘러쌓일때까지 구하고, 그 갯수를 파악해서 출력하면 된다. 혹은 BFS를 통해서 풀 수 있다. (복습을 할 때 BFS를 통해서 풀었다.)

1. 첫번째 풀이법

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    if x<=-1 or x>=n or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False
t = int(input())
for _ in range(t):
    m,n,k=map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    result=0
    for _ in range(k):
        x,y=map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                result+=1
    print(result)

dfs 함수를 정의해 주면서 먼저 x와 y좌표가 범위를 벗어날때는 False를 반환하게 두었다. 그러나 이렇게 하면 만약 x,y 에 (0,0) 이 들어갔을 경우 index error가 일어나게 된다. 

2. 두번째 풀이법

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    for i in range(4):
        nx,ny = x+dx[i],y+dy[i]
        if nx>=n or nx<0 or ny>=m or ny<0:
            continue
        if graph[nx][ny]==1:
            graph[nx][ny]=0
            dfs(nx,ny)
t = int(input())
for _ in range(t):
    m,n,k=map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    result=0
    for _ in range(k):
        x,y=map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                result+=1
    print(result)

두 번째 풀이법은 dx, dy를 통해서 상하좌우를 탐색하기 때문에 상관없지만 첫번째 풀이법은 의도치 않은 인덱스에 접근할 수 있기때문에 오류가 난다.

3. 세번째 풀이 (BFS를 통해서 해결)

BFS를 통해서 푸는 것으로 익숙해질려고 했다.(DFS를 사용하니까 계속 recursion error 같은 것들을 신경써야해서..) 먼저 BFS는 deque를 사용하므로 상단에 deque를 import 시켜준다.

from collections import deque

bfs는 파라미터로 a,b를 받는다. 여기서 a, b는 배추밭에서 1인 것, 즉 배추가 있는곳을 찾으면 bfs를 실행해서 주위가 0으로 둘러쌓인것에 닿을때까지 실행해준다. 그리고 bfs함수가 끝나면 total_num(우리가 출력해야 되는 값)을 하나 더해준다.

 매번 헷갈리지만 주의해야 할 것은 2차원 배열에 x,y축의 값이다.. 가로가 m이지만 배열의 첫번째는 y축의 값이 들어가는.. 이런것을 계속 생각해주어야 한다. 

from collections import deque
def bfs(a,b):
    q=deque([])
    q.append((a,b))
    graph[a][b]=0
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    bechu = 0
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<m and graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=0
t = int(input())
for _ in range(t):
    m,n,k = map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    total_num = 0
    for i in range(k):
        x,y = map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                bfs(i,j)
                total_num+=1
    print(total_num)

www.acmicpc.net/problem/2606

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1

4

[문제 해설]

문제 이해는 아주 잘 되는 편이였다. 1번이 바이러스에 걸리면 1번과 연결된 모든 컴퓨터가 바이러스에 걸린다. 1번에 의해서 몇개의 컴퓨터가 바이러스에 걸리는지 확인하면 되는 문제이다.

먼저 1부터 해서 깊게 파고들어서 연결된 컴퓨터를 모두 확인해야 되기 때문에 DFS를 떠올릴 수 있다. DFS를 통해서 풀었다.

(밑에 코드는 정답은 아니고 시행착오 중 하나)

n = int(input())
m= int(input())
computer=[]
visited=[False]*(n+1)

for i in range(m):
    computer.append(list(map(int,input().split())))

def dfs(computer,v,visited):
    visited[v]=True
    for i in range(m):
        x=computer[i][0]
        y=computer[i][1]
        if not visited[y] and x==v:
            dfs(computer,y,visited)
            print(visited)
dfs(computer,1,visited)
answer=0
for i in range(1,n+1):
    if visited[i]:
        answer+=1
print(answer-1)

위에 코드는 처음에 짠 코드이다. 연결된 간선 모두를 반복문을 통해 확인하고 방문되지 않은곳을 다 방문하여 확인하였다. 예제 입력에 있는 숫자들을 복사하면 출력 값이 잘 나온다.

 그러나 제출하면 계속 '틀렸습니다' 가 되어서 코드를 계속해서 보았다.

 예제 입력을 조금만 틀어서 입력하니까 문제를 찾을 수 있었다.

7
6
1 2
2 3
5 1#여기만 바꿈
5 2
5 6
4 7

사실 연결된 것은 똑같기 때문에 같은 값이 나와야 되는데 출력값은 4가 아니였다. 

양쪽에 연결된 것을 확인하지 않았기 때문이었다.

양쪽에 연결하는 코드를 추가해주면 된다.

n = int(input())
m= int(input())
computer=[]
visited=[False]*(n+1)

for i in range(m):
    computer.append(list(map(int,input().split())))

def dfs(computer,v,visited):
    visited[v]=True
    for i in range(m):
        x=computer[i][0]
        y=computer[i][1]
        if not visited[y] and x==v:
            dfs(computer,y,visited)
        if not visited[x] and y==v:
            dfs(computer,x,visited)
dfs(computer,1,visited)
answer=0
for i in range(1,n+1):
    if visited[i]:
        answer+=1
print(answer-1)

www.acmicpc.net/problem/2667

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1

3
7
8
9

[문제 풀이]

일단 <그림1>에서 1이 적힌 곳을 찾아서 0이 나올때까지 끝까지 탐색을 시켜줘야된다. 여기서 깊이 우선 탐색을 생각해 낼 수 있다. 지도에서 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.

n = int(input())
graph=[]#지도
apt=[]
for _ in range(n):
    graph.append(list(map(int,input())))

def dfs(x,y):
    global cnt
    if x<=-1 or x>=n or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        cnt+=1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False
cnt=0
for i in range(n):
    for j in range(n):
        if dfs(i,j)==True:
            apt.append(cnt)
            cnt =0
apt.sort()
print(len(apt))
for i in range(len(apt)):
    print(apt[i])

코드를 설명해보겠다.

일단 출력해야 되는 것은 2개이다. 아파트 단지의 개수와 단지 안에 아파트 수이다. apt 리스트에는 아파트 수가 담겨있게 하고 단지 수는 len(apt)로 구할 생각을 했다.

위에서 말했듯이 dfs로 풀었다. 일단 dfs함수에서 x,y 가 갈 수 없는 곳을 갔을 때는 False를 return해 주었다.

그리고 graph에서 값이 1일때 단지 수를 세면 되니까 1일때 graph의 값을 방문했다는 의미로 0을 대입해주고 아파트 수 즉 cnt를 1씩 늘여간다. 

그리고 dfs함수로 상, 하, 좌, 우를 방문한다.

n*n 반복문으로 apt를 구한다.

www.acmicpc.net/problem/2805

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7

20 15 10 17

예제 출력 1

15

[문제 해설]

H높이보다 큰 것은 (높이 - H)가 될 것이고 높이보다 작으면 잘리지 않을 것이다. 적당한 H 높이를 찾는 방법인데 최적의 길이를 찾아야되기 때문에 요리조리 해보면서 구해야 된다. 최적의 수를 찾는 것이기 때문에 sorting하는 방법이다. 알고리즘은 binary_search를 사용해서 풀면 시간도 적절하게 나온다. 

import sys
sys.stdin.readline

n,m = map(int,input().split())
tree=list(map(int,input().split()))

start = 1
end = max(tree)
ans=0

while start<=end:
    mid=(start+end)//2
    result=0
    for i in tree:
        if mid<i:
            result+=i-mid
    if result>=m:
        ans=mid
        start=mid+1
    elif result<m:
        end=mid-1
print(ans)