내 인생 이대로 ㅈ될 수 없다

2468번: 안전 영역 (acmicpc.net)

최근에 큰 비가 있었는데 어떻게 때를 맞춰서 풀어본 문제다.

문제의 포인트는 최대의 넓이를 갖는다는것이다.

즉 이말은 max_num 만큼 다 돌려주는게 포인트다.

내 풀이

from collections import deque
import sys

input = sys.stdin.readline


max_list=[]
N = int(input())
graph = [list(map(int,input().split())) for _ in range(N)]

def solution(x,y,max):
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    q = deque([(x,y)])
    visitied[x][y]=1
    
    while q:
        a,b = q.popleft()
        for i in range(4):
            nx = dx[i] + a
            ny = dy[i] + b
            
            if 0 <=nx < N and 0 <=ny <N:
                if graph[nx][ny] > max and visitied[nx][ny]==0:
                    visitied[nx][ny]=1
                    q.append((nx,ny))

max_num = 0
result=0
for i in graph:
  for j in i:
    if max_num < j:
      max_num = j                
      
                    
for k in range(max_num):
    count=0
    visitied = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if graph[i][j] > k and visitied[i][j]==0:
                solution(i,j,k)
                count +=1
    if result < count :
        result = count
print(result)​

흔한 bfs다. 꽤 많이 풀다보니 이제는 진짜 많이 익숙해진 듯 하다. 

다른사람의 풀이

한동안 토이프로젝트 진행한다고 안올렸었는데 다시 열심히 해봐야 겠다.

https://www.acmicpc.net/problem/14502

내 풀이

from itertools import combinations

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
tmp = [[0]*m for _ in range(n)]

def virus(x, y):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    
    for k in range(4):
        xx = x+dx[k]
        yy = y+dy[k]
        if 0<=xx<n and 0<=yy<m and tmp[xx][yy] == 0:
            tmp[xx][yy] = 2
            virus(xx, yy)


def count():
    cnt = 0
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 0:
                cnt += 1
    return cnt


def solution():
    result = 0
    

    
    zeroIdxs = []
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                zeroIdxs.append((i, j))

    for coordinates in list(combinations(zeroIdxs, 3)):
        
        for x,y in coordinates:
            board[x][y] = 1

        
        for i in range(n):
            for j in range(m):
                tmp[i][j] = board[i][j]

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

        result = max(result, count())
       
        for x,y in coordinates:
            board[x][y] = 0
    return result


print(solution())

이 문제 푸려고 진짜 오래고민했다. 거의 이주는 고민한듯..

근데 오늘 비슷한 유형의 문제를 풀면서 이해했다 드디어!

이 문제의 핵심이 무엇이냐

1) 벽을 세울 수 있는 모든 지점에 벽을 세운다. -> solution()을 통해

2) 바이러스를 모두 퍼뜨린다 -> virus() 을 통해

3) 넓이를 구한다.  -> count() 을 통해

4) 넓이를 구해서 최대값과 비교한다.  

5) 모든 경우의 수에 반복한다.

다른사람의 풀이

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

N, M = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(N)] # 그래프 생성
graph_copy = copy.deepcopy(graph) # 그래프 복사
dx, dy = [-1,1,0,0], [0,0,-1,1] # 상하좌우 이동

safe_region = 0 # 최대 안전 영역

# dfs
def dfs(x,y,sel_wall):
    sel_wall[x][y] = 2 # 바이러스로 변경

    # 상하좌우 탐색
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if sel_wall[nx][ny] == 0: # 바이러스가 퍼질 수 있는 곳
                dfs(nx,ny,sel_wall) # 바이러스 퍼뜨리기


# 벽 선택하기
def select_wall(start, count):
    global safe_region

    if count == 3: # 벽이 3개 선택된 경우 실행
        sel_wall = copy.deepcopy(graph_copy) # 벽이 선택된 그래프 복사
        # dfs로 바이러스 퍼뜨리기
        for i in range(N):
            for j in range(M):
                if sel_wall[i][j] == 2: # 바이러스 발견시에 dfs
                    dfs(i,j,sel_wall)
        safe_count = sum(_.count(0) for _ in sel_wall) # 안전 영역 개수 계산
        safe_region = max(safe_region,safe_count) # 최대 안전 영역 개수 갱신
        return

    else: # 벽이 3개 선택되지 않은 경우
        for i in range(start, N*M): # 브루트-포스로 벽 선택
            r = i // M # M으로 나눈 몫는 행
            c = i % M # M으로 나눈 나머지는 열
            if graph_copy[r][c] == 0: # 해당 구역이 0인 경우에
                graph_copy[r][c] = 1 # 벽으로 선택
                select_wall(i,count+1) # 다음 벽 선택
                graph_copy[r][c] = 0 # 되돌리기

select_wall(0,0)
print(safe_region)

COMBINATION을 사용하지 않고도 풀이가 가능할거 같은데, 파이썬으로 돌리면 시간초과가 난다.

그 부분에 대해서는 조금 고민 해봐야 할거같다.

https://www.acmicpc.net/problem/16236

내 풀이

from collections import deque
import sys
INF = 10**8
input = sys.stdin.readline

def solution():
    K = int(input())
    graph = [list(map(int,input().split())) for _ in range(K)]

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

    shark = 2
    now_x,now_y=0,0

    for i in range(K):
        for j in range(K):
            if graph[i][j]==9:
                now_x,now_y = i,j
                graph[now_x][now_y] = 0


    def bfs():
        dist = [[-1] * K for _ in range(K)]
        q = deque([(now_x,now_y)])
        dist[now_x][now_y]=0

        while q:
            a,b = q.popleft()
            for i in range(4):
                nx = dx[i] + a
                ny = dy[i] + b

                if 0<=nx <K and 0<=ny <K:
                    if dist[nx][ny] == -1 and graph[nx][ny] <= shark:
                        dist[nx][ny] = dist[a][b] + 1
                        q.append((nx,ny))
        return dist


    def find(dist):
        x,y=0,0
        min_dist=INF
        for i in range(K):
            for j in range(K):
                if dist[i][j] != -1 and 1<= graph[i][j] <shark:
                    if dist[i][j] < min_dist:
                        x,y = i,j
                        min_dist = dist[i][j]
                        
        if min_dist == INF:
            return None
        else:
            return x,y,min_dist
        
    result =0
    ate = 0

    while True:
        value = find(bfs())

        if value == None:
            print(result)
            break
        else:
            now_x,now_y = value[0],value[1]
            result += value[2]

            graph[now_x][now_y]=0
            ate +=1

            if ate >= shark:
                shark +=1
                ate = 0
solution()

다른 사람들의 풀이를 보니까 정렬을 했던데, 사실 그럴 필요가 없다고 생각했다. 왜냐면 애초에 최단 거리 테이블을 제공하면 되기때문이다.

bfs로 최단 거리 테이블을 제공, find함수로 가장 가까운 물고기 1마리를 선택하면 된다.

True 인동안 최단 거리에 있는 물고기를 계속해서 탐색하면 될일이다. 

시간 초과의 위험역시 먹을 물고기가 없는 경우에는 바로 함수가 종료되므로 걱정할 일이 없다.

다른사람의 풀이

from collections import deque
n = int(input())
s_x, s_y = -1, -1
s_level, eat = 2, 0
graph = []

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

for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(n):
        if data[j] == 9:
            s_x, s_y = i, j


graph[s_x][s_y] = 0

def bfs(s_x, s_y, s_level):
    visited = [[False]*n for _ in range(n)]
    q = deque()
    q.append((s_x, s_y, 0))
    visited[s_x][s_y] = True
    fish = []
    while q:
        x, y, count = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                if graph[nx][ny] != 0 and graph[nx][ny] < s_level:
                    fish.append((count+1, nx, ny))
                    q.append((nx, ny, count+1))
                    visited[nx][ny] = True
                elif graph[nx][ny] == 0 or graph[nx][ny] == s_level:
                    visited[nx][ny] = True
                    q.append((nx, ny, count+1))

    fish.sort()
    if fish:
        return [fish[0][1], fish[0][2], fish[0][0]]
    else:
        return []

answer = 0

while True:
    fish_eat = bfs(s_x, s_y, s_level)
    if fish_eat:
        x, y, move = fish_eat
        graph[x][y] = 0
        eat += 1
        answer += move
        if eat == s_level:
            s_level += 1
            eat = 0
        s_x, s_y = x, y
    else:
        break

print(answer)

https://www.acmicpc.net/problem/1707

내 풀이

1.BFS

import sys
from collections import deque

input = sys.stdin.readline



def bfs(start):
    queue = deque([start])  
    visited[start] = 1   
    while queue:  
        x = queue.popleft()  

        for i in graph[x]:  
            if not visited[i]:  
                queue.append(i)  
                visited[i] = -1 * visited[x]  
            elif visited[i] == visited[x]:  
                return False  
    return True  


for _ in range(int(input())):
    V, E = map(int, input().split())
    graph = [[] for i in range(V + 1)]  
    visited = [False] * (V + 1)  

    for _ in range(E):
        a, b = map(int, input().split())
        graph[a].append(b)  
        graph[b].append(a)  

    for i in range(1, V + 1):
        if not visited[i]:  
            result = bfs(i)
            if not result:
                break

    print('YES' if result else 'NO')

우선 문제를 이해하는게 조금 이해가 안됐다. 

내가 이해한 바로는 이렇다.

어떤 노드들을 두 그룹으로 나눌 수 있냐를 판단하는데 

그 기준은 같은 그룹에 있는 인접한 노드들끼리는 간선이 연결 되어 있지 않아야한다.

즉 같은 그룹안에 있는 노드들은 서로 연결이 되어 있으면 안된다.

같은 그룹인지를 판단하기 위해서 visited에 0(방문한적이 없음),1(그룹 1),-1(다른 그룹 -1) 을 할당한다.

같은 그룹일 경우에는 False를 반환한다.

2. DFS

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

def solution():
    def dfs(start,group):
        nonlocal error
        if error:
            return

        visited[start] = group

        for i in graph[start]:
            if not visited[i]:
                dfs(i,-group)
            elif visited[start] == visited[i]:
                error = True
                return

    for _ in range(int(input())):
        V, E = map(int, input().split())
        graph = [[] for _ in range(V + 1)]  
        visited = [False] * (V + 1)  
        error = False

        for _ in range(E):
            a, b = map(int, input().split())
            graph[a].append(b)
            graph[b].append(a)

        for i in range(1, V + 1):
            if not visited[i]:  
                dfs(i, 1)  
                if error:  
                    break  

        if error:
            print('NO')
        else:
            print('YES')

solution()

개인적으로 이 문제는 dfs가 조금 더 직관적인거 같다. 위와 같은 개념이다!

다른사람의 풀이

https://ji-gwang.tistory.com/293

참고 블로그

이 문제를 끝으로 bfs를 모두 끝냈다.

조금 익숙해지긴 했지만 아직까지도 확실하지는 않다.

매일매일 반복해야겠다

내 풀이

import sys
from collections import deque

input = sys.stdin.readline

def solution():
    N,M = map(int,input().split())
    graph=[i for i in range(101)]
    visited = [0] * 101
    for i in range(N+M):
        a,b = map(int,input().split())
        graph[a]=b
    def bfs():
        queue = deque([1])
        visited[1] = 1

        while queue:

            x = queue.popleft()
            print(x)

            for i in range(1,7):
                dice = x + i

                if dice > 100:
                    continue

                cnt = graph[dice]

                if visited[cnt]==0:
                    queue.append(cnt)
                    visited[cnt] = visited[x] + 1

                    if cnt == 100:
                        return
    bfs()
    print(visited[100]-1)
solution()

BFS로 풀어봤다.

포인트는, graph에다가 이동하는 숫자만큼 배분하는것이다.

가령 4에 78로 움직이는 사다리가 있다고 가정하면

graph[4] = 78로 대체하는것이다. 그 외에는 해당 숫자에 맞는 크기를 배분해준다.

배분된 숫자에 주사위 크기만큼 (1~6) 더해주고 그 크기가 100을 넘어간다면 continue를 통해 무시해준다. 

주사위 자체가 1~6까지 for 문으로 돌아가기 때문에

x+1~x+6,까지는 visited[x]의 값이 같을 수 밖에 없다. 

최초에 visited[1]= 1 로 시작하기 때문에 마지막에 -1을 해준다.

참고로 print(x) 주석처리 해줘야 오류 안뜬다.

다른사람의 풀이

from collections import deque

def bfs():
    queue = deque([1])
    visited[1] = True
    while queue:
        now = queue.popleft()
        for move in range(1,7):
            check_move = now+move
            if 0 < check_move <= 100 and not visited[check_move]:
                if check_move in ladder.keys():
                    check_move = ladder[check_move]

                if check_move in snack.keys():
                    check_move = snack[check_move]

                if not visited[check_move]:
                    queue.append(check_move)
                    visited[check_move] = True
                    board_cnt[check_move] = board_cnt[now] + 1



if __name__ == '__main__':
    N, M = map(int,input().split())
    board_cnt = [0] * 101
    visited = [False] * 101

    snack = dict()
    ladder = dict()
    for _ in range(N):
        i,j = map(int,input().split())
        ladder[i] = j
    for _ in range(M):
        i,j = map(int,input().split())
        snack[i] = j

    bfs()
    print(board_cnt[100])

딕셔너리를 이용하여 풀었다. 기본적인 접근자체는 비슷한거 같다. 근데 이렇게하면 처리를 각각해줘야 되니 귀찮을거 같다.

https://www.acmicpc.net/problem/1504

내 풀이

import sys
import heapq

INF = int(1e9)
input = sys.stdin.readline
def solution():
    N,E = map(int,input().split())
    graph = [[] for _ in range(N+1)]

    for _ in range(E):
        a,b,c = map(int,input().split())
        graph[a].append((b,c))
        graph[b].append((a,c))
    
    def ekdlrtmxmfk(start):
        distance = [INF] * (N+1)
        distance[start]=0
        q=[]
        heapq.heappush(q,(0,start))
        while q:
            dist,now = heapq.heappop(q)
            if distance[now] < dist:
                continue
            for i in graph[now]:
                cost = i[1] + dist
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q,(cost,i[0]))
        return distance
    
    
    x,y = map(int,input().split())

    original = ekdlrtmxmfk(1)
    #print(original)
    p1=ekdlrtmxmfk(x)
    #print(p1)
    p2=ekdlrtmxmfk(y)
    #print(p2)
    p1_path = original[x] + p1[y] + p2[N]
    p2_path = original[y] + p2[x] + p1[N]

    #print(p1_path,p2_path)
    answer = min(p1_path,p2_path)

    print(answer if answer <INF else -1)


solution()

최초에 문제 이해가 안됐다. 특정 노드를 반드시 거쳐가야한다는게 무슨말이지?

어차피 특정 노드를 거쳐가야하지않나?

잘 생각해보니

주어진 노드가 a,b,c,d 이고 특정 노드가 b,c라고하면

a -> d -> b- >c

혹은 

a -> c ->d ->b

이런식으로도 갈 수 있는데 이런 경우는 배제하고

무조건

a -> b -> c -> d 혹은

a -> c->b ->d 의 순서로 가라는 뜻이였다.

그러니까 최초 시작점 to 특정노드1 + 특정노드 1 to 특정노드 2 + 특정노드2 to 끝까지 or

               최초 시작점 to 특정노드2 + 특정노드 2 to 특정노드 1  + 특정노드1 to 끝까지 

중 최소 값을 택하면되는거다.  

다른사람의 풀이

import sys; input = sys.stdin.readline
from heapq import heappush, heappop

def dijkstra(start, end):
    dis = [0xffffff] * (N + 1)
    dis[start] = 0
    q = [[0, start]]
    while q:
        k, u = heappop(q)
        if k > dis[u]: continue
        for w, v in G[u]:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                heappush(q, [dis[v], v])

    return dis[end]

N, E = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    G[u].append([w, v])
    G[v].append([w, u])

stop1, stop2 = map(int, input().split())

# 1 -> stop1 -> stop2 -> N
path1 = dijkstra(1, stop1) + dijkstra(stop1, stop2) + dijkstra(stop2, N)
# 1 -> stop2 -> stop1 -> N
path2 = dijkstra(1, stop2) + dijkstra(stop2, stop1) + dijkstra(stop1, N)

if path1 >= 0xffffff and path2 >= 0xffffff:
    print(-1)
else:
    print(min(path1, path2))