내 인생 이대로 ㅈ될 수 없다

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

내 풀이

from collections import deque
import sys

input = sys.stdin.readline

def solution():
    n,m = map(int,input().split())
    graph=[list(input().strip()) for _ in range(n)]
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    def bfs(x,y):
        visit = [[0]* m for _ in range(n)]
        visit[x][y]=1
        q = deque([(x,y)])
        
        
        
        while q:
            x,y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0>nx or nx>=n or 0>ny or m<=ny or graph[nx][ny]=='W' or visit[nx][ny]  :
                    continue
                
                visit[nx][ny] = visit[x][y] + 1             
                q.append((nx,ny))
        
        return visit[x][y]-1
    max_time=0  
    for i in range(n):
        for j in range(m):
            if graph[i][j]=='L':
                if 0<=i-1 and i+1<n:
                    if graph[i-1][j]=='L' and graph[i+1][j]=='L':
                        continue
                if 0<=j-1 and j+1<m:
                    if graph[i][j-1]=='L'and graph[i][j+1]=='L':
                        continue
                max_time=max(bfs(i,j),max_time)
    print(max_time)
                
solution()

문제 자체는 진짜 평이했는데 그놈의 시간초과가 나를 괴롭혔다.

당연히 pypy로 풀면 해결되지만 코딩테스트에서는 pypy를 지원하지 않는 경우가 많아서 꼭 파이썬으로 풀고 싶었다.

조건을 조금 더 생각해보니, 그래프에서 양 옆이 모두 육지인 경우는 절대 최대값일 수가 없었다.

가령

LLW

LWW

LLL

이런 그래프가 있다하면

그래프에서 (0,2)인 지점은 절대 최대값일 수가 없다 왜?

내 옆에 땅을 거쳐가면 반드시 현재 위치보다 더 긴시간이 걸릴테니까

이런 문제의 핵심은 적어도 파이썬으로 풀때는, 숨겨진 조건을 찾는것인거 같다.

다른사람의 풀이

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
bomool = []
land = []
for i in range(N):
    temp = list(map(str, input()))
    for j in range(len(temp)):
        if temp[j] == 'L':
            land.append((i, j))
    bomool.append(temp)

dr = [-1, 0, 1, 0]  # 행 상 우 하 좌
dc = [0, 1, 0, -1]  # 열 상 우 하 좌


def bfs(r, c):
    queue = deque([[r, c, 0]])
    visited[r][c] = True
    while queue:
        r, c, distance = queue.popleft()

        for i in range(4):

            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nr >= N or nc < 0 or nc >= M or visited[nr][nc] or bomool[nr][nc] == 'W':
                continue

            visited[nr][nc] = True
            queue.append([nr, nc, distance + 1])

    return distance


max_ = 0
for i in range(len(land)):
    visited = [[False] * M for _ in range(N)]
    distance = bfs(land[i][0], land[i][1])
    if max_ < distance:
        max_ = distance

print(max_)

https://ji-gwang.tistory.com/m/406

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

내 풀이

import sys
from collections import deque

input = sys.stdin.readline

def solution():
    ans=[]
    
    n,m = map(int,input().split())
    graph=[[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    def bfs(v):
        q = deque([v])
        visited[v]=1
        print('q=',q)

        while q:
            node = q.popleft()
            print('node=',node)

            for i in graph[node]:
                print('i=',i)
                if not visited[i]:
                    visited[i] = visited[node] + 1
                    q.append(i)
        print('visited=',visited)

    for i in range(1,n+1):
        visited=[0]*(n+1)
        bfs(i)
        ans.append(sum(visited))

    for i in range(len(ans)):
        if ans[i]==min(ans):
            print(i+1)
            return

solution()

5 5
1 3
1 4
4 5
4 3
3 2
q= deque([1])
node= 1
i= 3
i= 4
node= 3
i= 1
i= 4
i= 2
node= 4
i= 1
i= 5
i= 3
node= 2
i= 3
node= 5
i= 4
visited= [0, 1, 3, 2, 2, 3]
q= deque([2])
node= 2
i= 3
node= 3
i= 1
i= 4
i= 2
node= 1
i= 3
i= 4
node= 4
i= 1
i= 5
i= 3
node= 5
i= 4
visited= [0, 3, 1, 2, 3, 4]
q= deque([3])
node= 3
i= 1
i= 4
i= 2
node= 1
i= 3
i= 4
node= 4
i= 1
i= 5
i= 3
node= 2
i= 3
node= 5
i= 4
visited= [0, 2, 2, 1, 2, 3]
q= deque([4])
node= 4
i= 1
i= 5
i= 3
node= 1
i= 3
i= 4
node= 5
i= 4
node= 3
i= 1
i= 4
i= 2
node= 2
i= 3
visited= [0, 2, 3, 2, 1, 2]
q= deque([5])
node= 5
i= 4
node= 4
i= 1
i= 5
i= 3
node= 1
i= 3
i= 4
node= 3
i= 1
i= 4
i= 2
node= 2
i= 3
visited= [0, 3, 4, 3, 2, 1]
3

개인적으로 이 문제 bfs 공부하기 굉장히 좋은 문제라고 생각한다.

하여 좀 귀찮지만 모든 로그를 찍어보기 위하여 위와 같이 결과 값도 첨부한다

bfs의 가장 큰 특징은 가까운 정점부터 방문한다는 것이다.

위 문제에서 최초 1이 들어가게되면 

visited의 형태는 = [0,1,0,0,0,0] 

graph = [[],[3,4],[3],[1,4,2],[4]] 

이런식일 테다.

bfs 를 풀때마다 최초에 visited에 1을 넣는것이 좀 의아했었다. 근데 이렇게 로그로 찍어보니까 어차피 모든 visited에 1을 더해주니까 결과값에는 영향이 없다는것을 눈으로 확인 할 수 있었다.

다른사람의 풀이

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

내 풀이

import sys
from collections import deque

input = sys.stdin.readline

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

def check(x,y,nx,ny):
    count = 0 
    while graph[x+nx][y+ny] !='#' and graph[x][y]!='O':
        x += nx
        y += ny
        count +=1
    return x,y,count

def solution():
    for i in range(n):
        for j in range(m):
            if graph[i][j]=='R':
                rx,ry = i,j
            elif graph[i][j]=='B':
                bx,by = i,j
    #q = deque([(rx,ry,bx,by,1)])
    q = deque()
    q.append([rx,ry,bx,by,1])
    visited[rx][ry][bx][by]=True
    

    while q:
        rx,ry,bx,by,count = q.popleft()
        
        if count > 10:
            break
        for i in range(4):
            nrx,nry,rcount = check(rx,ry,dx[i],dy[i])
            nbx,nby,bcount = check(bx,by,dx[i],dy[i])

            if graph[nbx][nby] !='O':
                if graph[nrx][nry] =='O':
                    return count
                if nrx == nbx and nry == nby:
                    if rcount > bcount :
                        nrx -= dx[i]
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]

                if not visited[nrx][nry][nbx][nby]:
                    visited[nrx][nry][nbx][nby] = True
                    q.append((nrx,nry,nbx,nby,count+1))
    return -1
    

print(solution())

포인트는 두 구슬중에 어떤것이 앞선 구슬인가를 구하는 방법이다.

다른사람의 풀이

N, M = map(int, input().split())
B = [list(input().rstrip()) for _ in range(N)]  # Board
dx = [-1, 1, 0, 0]  # x축 움직임
dy = [0, 0, -1, 1]  # y축 움직임
queue = []  # BFS : queue 활용
# Red(rx,ry)와 Blue(bx,by)의 탐사 여부 체크
visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]

def pos_init():
    rx, ry, bx, by = 0, 0, 0, 0  # 초기화
    for i in range(N):
        for j in range(M):
            if B[i][j] == 'R':
                rx, ry = i, j
            elif B[i][j] == 'B':
                bx, by = i, j
    # 위치 정보와 depth(breadth 끝나면 +1)
    queue.append((rx, ry, bx, by, 1))
    visited[rx][ry][bx][by] = True

def move(x, y, dx, dy):
    cnt = 0  # 이동 칸 수
    # 다음이 벽이거나 현재가 구멍일 때까지
    while B[x+dx][y+dy] != '#' and B[x][y] != 'O':
        x += dx
        y += dy
        cnt += 1
    return x, y, cnt

def solve():
    pos_init()  # 시작 조건
    while queue:  # BFS : queue 기준
        rx, ry, bx, by, depth = queue.pop(0)
        if depth > 10:  # 실패 조건
            break
        for i in range(4):  # 4방향 이동 시도
            nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])  # Red
            nbx, nby, bcnt = move(bx, by, dx[i], dy[i])  # Blue
            if B[nbx][nby] != 'O':  # 실패 조건이 아니면
                if B[nrx][nry] == 'O':  # 성공 조건
                    print(depth)
                    return
                if nrx == nbx and nry == nby:  # 겹쳤을 때
                    if rcnt > bcnt:  # 이동거리가 많은 것을
                        nrx -= dx[i]  # 한 칸 뒤로
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]
                # breadth 탐색 후, 탐사 여부 체크
                if not visited[nrx][nry][nbx][nby]:
                    visited[nrx][nry][nbx][nby] = True
                    # 다음 depth의 breadth 탐색 위한 queue
                    queue.append((nrx, nry, nbx, nby, depth+1))
    print(-1)  # 실패 시

solve()

https://wlstyql.tistory.com/72

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)