수학과의 개발자 도전기

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

-정답풀이:

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

-문제 해결방법 생각해본 거:

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

-정답풀이:

from collections import deque

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

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

sx, sy = 0, 0
for i in range(n):
    for j in range(n):
        if arr[i][j] == 9:
            arr[i][j] = 0
            sx, sy = i, j
            break
size = 2
move_num = 0
eat = 0
while True:
    q = deque()
    q.append((sx, sy, 0))
    visited = [[False] * n for _ in range(n)]
    flag = 1e9
    fish = []
    while q:
        x, y, count = q.popleft()

        if count > flag:
            break
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if arr[nx][ny] > size or visited[nx][ny]:
                continue

            if arr[nx][ny] != 0 and arr[nx][ny] < size:
                fish.append((nx, ny, count + 1))
                flag = count
            visited[nx][ny] = True
            q.append((nx, ny, count + 1))

    if len(fish) > 0:
        fish.sort()
        x, y, move = fish[0][0], fish[0][1], fish[0][2]
        move_num += move
        eat += 1
        arr[x][y] = 0
        if eat == size:
            size += 1
            eat = 0
        sx, sy = x, y
    else:
        break

print(move_num)

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

채점까지 오래걸렸던 문제.

스스로 풀이 없이 푼 문제다 

처음에 dfs로 풀다가 setrecursionlimit(100000)까지 걸었는데 70몇퍼에서 recursionerror가 발생했다

그래서 bfs로 바꿨더니 맞은 문제

silver level2 문제 

-정답풀이:

from collections import deque

n=int(input())
graph=[[] for _ in range(n+1)]
ans=[0]*(n+1)

#그래프 정리 
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
visit=[0]*(n+1)    

def bfs(v):
    queue=deque()
    queue.append(v)
    visit[v]=1
    while queue:
        x=queue.popleft()
        for i in graph[x]:
            if not visit[i]:
                visit[i]=1
                queue.append(i)
                ans[i]=x
                
bfs(1)            
for i in range(2,n+1):
    print(ans[i])

-RecursionError 발생

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

2776번, 단지 붙이기와 같은 유형의 문제다

bfs문제로 풀기 어렵지 않은 문제다

스스로 푼 문제. silver level1이다 

문제에서 갯수와 각각의 빈공간의 갯수 출력하는 건데 잘 안보고 풀었더니 초반에 몇번 틀렸다.

문제 자세히 보는 건 기본!!

-주의 해야할 부분: 

1. bfs를 보면 ans=0에서 시작하기 때문에 처음 시작하는 한 칸의 갯수를 덜 센다

그래서 각각의 결과에 1을 더해줘야한다. 이거 때문에 마지막에 꽤 시간을 소요했다

2. 주어진 순서대로 행,열이라고 생각했는데 주어진 위치와 테이블 인덱스는 반대이므로 a,b,c,d로 받고

(b,a),(d,c) 순서로 생각하고 직사각형을 채워야한다 

-정답풀이: 

from collections import deque
m,n,k=map(int,input().split())
graph=[[0]*n for _ in range(m)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
#사각형 있는 곳 채우기(b,a)~(d,c)
for _ in range(k):
    a,b,c,d=map(int,input().split())
    for i in range(b,d):
        for j in range(a,c):
            graph[i][j]=1
            
def bfs(x,y):
    global ans
    queue=deque()
    queue.append([x,y])
    graph[x][y]=1
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<m and 0<=ny<n:
                if graph[nx][ny]==0:
                    graph[nx][ny]=1
                    queue.append([nx,ny])
                    ans+=1
ans=0
cnt=0
result=[]
for i in range(m):
    for j in range(n):
        if graph[i][j]==0:
            bfs(i,j)
            cnt+=1
            result.append(ans)
            ans=0
print(cnt)
result.sort()
for i in range(cnt):
    print(result[i]+1,end=' ')

-틀린풀이: