수학과의 개발자 도전기

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

처음에는 한 값을 기준으로 dfs를 돌린 후 다음 값을 dfs 돌릴때 방문했던 노드를 방문하면 그것이 최소 공통조상이라고 생각하고 코드를 짰는데 계속 IndexError가 발생했다

그래서 그럼 각각의 부모노드들을 리스트로 만들어서 그것을 하나하나 비교하다가 처음으로 같은 것을 출력하면될 것이라고 생각했는데

이걸 dfs함수로 구현하면 각각 다른 리스트를 반환할텐데 그걸 어떻게 해야하나 싶은 생각이 들었다. global result같은 것을 못 쓸 것 같아서 찾아보니 그냥 while문으로 돌리고, 값을 하나씩 옮기는 식으로 진행하면된다 

그리고 최소 공통 부모는 각 리스트의 끝(루트노드)부터 내려와서 같지 않은 노드가 나올때까지 반복한 후, 처음으로 같지 않은 노드가 나왔을 때 노드의 부모가 최소공통조상이라고 할 수 있다

-정답풀이: 

t=int(input())
for _ in range(t):
    n=int(input())   
    graph=[0]*(n+1)
    for _ in range(n-1):
        a,b=map(int,input().split())
        graph[b]=a
    x,y=map(int,input().split())
    x_list=[x]
    y_list=[y]
    while graph[x]:
        x_list.append(graph[x])
        x=graph[x] #자식노드에서 부모노드로 이동
    while graph[y]:
        y_list.append(graph[y])
        y=graph[y]
    x_level=len(x_list)-1 #이 인덱스는 모두 루트 노드
    y_level=len(y_list)-1
    
    while x_list[x_level]==y_list[y_level]: 
        x_level-=1
        y_level-=1
    print(x_list[x_level+1])

-틀린풀이: 

def dfs(v):
    visit[v]=1
    for i in graph[v]:
        if visit[i]:
            print(i)
            exit()
        if not visit[i]:
            dfs(i)
            
t=int(input())
for _ in range(t):
    n=int(input())
    visit=[0]*(n+1)
    graph=[[]*(n+1)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        graph[b].append(a)
    x,y=map(int,input().split())
    dfs(x)
    dfs(y)

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

무한루프를 도는 조건이 사실 어떤 원리로 발생하는지 이해가 가지 않았다. 

찾아보니 방문했던 곳을 한번 더 방문하면 무한루프가 돌 가능성이 있어서 이것을 바탕으로 -1을 출력하면된다 

방문한 횟수를 dp 행렬을 따로 만들어 이용함으로써 시간초과를 방지할 수 있다고 한다 

마지막에 주의할 점은 ans값을 구했어도 마지막에 바깥으로 빠지거나 구멍에 빠질때도 한번 더 움직이는 것이므로 ans+1을 해주어야한다

참고한 블로그

-정답풀이:

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

n,m=map(int,input().split())
s=[list(map(str,input())) for _ in range(n)]
visit=[[0]*m for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

ans=0
dp=[[0]*m for _ in range(n)]
def dfs(x,y,cnt):
    global ans
    ans=max(ans,cnt)
    visit[x][y]=1
    k=int(s[x][y])
    for i in range(4):
        nx,ny=x+dx[i]*k,y+dy[i]*k
        if 0<=nx<n and 0<=ny<m and s[nx][ny]!='H' and cnt+1>dp[nx][ny]:
            if visit[nx][ny]:
                print(-1)
                exit()
            else:
                dp[nx][ny]+=1
                visit[nx][ny]=1
                dfs(nx,ny,cnt+1)
                visit[nx][ny]=0
dfs(0,0,0)
print(ans+1)

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

처음에는 dfs로 풀려고 했는데, 잘 풀리지 않아서 bfs로 풀어보았다. 

그런데 함수의 값을 반환해서 어떻게 해보려고 했는데 그게 잘 되지 않아 구글링을 했다.

찾아보니 bfs가 끝났을 때 s 행렬을 바꿔주는 방식으로 진행하면 따로 반환없이 바로 출력하면 된다 

찾아보니 이 블로그가 설명이 더 깔끔한 것 같다. 이거를 기준으로 다시 공부 해봐야할 것 같다

참고한 블로그

-정답풀이:

from collections import deque

def bfs(cur_r,cur_c,itr):
    q=deque()
    q.append([cur_r,cur_c])
    v[cur_r][cur_c]=itr
    cnt=1
    tmp=[]
    while q:
        x, y=q.popleft()
        for dx, dy in dr:
            nx, ny=x+dx, y+dy
            if 0<=nx<n and 0<=ny<m and v[nx][ny]!=itr:
                if not a[nx][ny]:
                    q.append([nx, ny])
                    v[nx][ny]=itr
                    cnt+=1
                else:
                    tmp.append([nx, ny])
                    v[nx][ny]=itr
    for i, j in tmp:
        c[i][j] += cnt
        
n,m=map(int,input().split())
a=[list(map(int,input())) for _ in range(n)]
v=[[0]*m for _ in range(n)]
c=[[0]*m for _ in range(n)]
dr=[[-1,0],[1,0],[0,-1],[0,1]]
itr=1
for i in range(n):
    for j in range(m):
        if a[i][j]:
            c[i][j]=1
for i in range(n):
    for j in range(m):
        if not a[i][j] and not v[i][j]:
            bfs(i,j,itr)
            itr+=1
for i in range(n):
    for j in range(m):
        print(c[i][j] % 10, end='')
    print()

-틀린풀이:

나름 작성해본 코드인데 함수에서 반환하는 것을 잘 못해서 TypeError가 발생했다 

함수에 대해 공부해야할 것 같다,,,

from collections import deque
n,m=map(int,input().split())
s=[list(map(int,list(input()))) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
ones=[]
for i in range(n):
    for j in range(m):
        if s[i][j]==1:
            ones.append([i,j])
def bfs(x,y):
    q=deque()
    q.append((x,y))
    cnt=1
    while q:
        x,y=q.popleft()       
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx <n and 0<=ny<m:
                if not s[nx][ny]:
                    cnt+=1
                    q.append((nx,ny))
                else:
                    continue 
    return cnt
for i in range(len(ones)):
    for x,y in ones[i]:
        ans=bfs(x,y)
        s[x][y]=ans%10
for i in range(n):
    print(s[i])

오류 발생한 부분

2022.08.09

IDE에서 오류나는 걸로 다음과 같이 코드 작성했더니 정상작동했다 

이때는 아직 코드작성이 더 미숙해서 겪었던 문제였던 것 같다 

for x,y in ones :
    ans = bfs(x,y)
    s[x][y] = ans % 10

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

꽤 쉬운 문제라고 생각했는데 찾아보니 그리 쉽지 않은 문제라서 추가로 공부를 해야할 것 같다

참고한 블로그 

전형적인 백트래킹 문제이고, 조합으로 접근하는 문제다

dfs함수로 25개의 칸에서 7개의 칸을 선택하는 조합을 구현한다 

0부터 24까지의 숫자를 5*5행렬의 좌표로 변환해주며 탐색한다( 23번은 4행 3열에 위치해있다)

해당 위치가 'Y'이면 ycnt+1하며 재귀로 넘겨주고, 'S'라면 그냥 인자를 그대로 넘긴다 

depth도 사용하지 않고, ycnt도 사용하지 않고 인덱스만 넘기는 경우가 있어서(이런 경우가 어떻게 있지?) dfs(depth,ycnt,idx+1)을 추가한다

백트래킹으로 Y를 4번 이상 만났다면 return하여 가지치기를 함으로써 어느정도 거를 수 있다. 밑에서 ycnt>=4인 경우다.

(가지치기가 무엇?) 위 상황말고도 탐색할 숫자가 나의 남은 선택 수보다 작으면 가지치기를 해준다

check함수를 통해 7개의 자표들이 서로 연결된 좌표인지 확인한다

0-24까지의 숫자를 5*5행렬 위치로 변환하고, 4방향 탐색을 통해 갈 수 있는 곳의 숫자가 현재 조합 숫자에 포함된 숫자라면 

재귀를 돌린다 

매 조합의 경우마다 visit와 available 변수를 초기화해줘야 한다

available==7인 경우는 7개의 위치 좌표가 서로 연결된 것이므로 result+=1을 해준다 

-정답풀이: 

nextNum+= nr*5+nc로 써서 계속 UnboundLocalError 발생해서 고생했다,,

from sys import stdin
input=stdin.readline
dr=[-1,1,0,0]
dc=[0,0,-1,1]

def check(num):
    global available 
    r=num//5
    c=num%5
    for i in range(4):
        nr,nc=r+dr[i],c+dc[i]
        if 0<=nr<5 and 0<=nc<5 and not visit[nr][nc]:
            nextNum=nr*5+nc
            if nextNum in p:
                visit[nr][nc]=1
                available+=1
                check(nextNum)
                
#깊이, Y의 갯수, 사용할 숫자 인덱스                 
def dfs(depth,ycnt,idx):
    global result,available,visit
    if ycnt>3 or 25-idx <7-depth: #가지치기 
        return 
    if depth==7:
        available=1
        visit=[[0]*5 for _ in range(5)]
        sr,sc=p[0]//5,p[0]%5
        visit[sr][sc]=1
        check(p[0])
        if available ==7:
            result+=1
        return 
    r=idx//5
    c=idx%5
    
    if A[r][c]=='Y':
        p.append(idx)
        dfs(depth+1,ycnt+1,idx+1)
        p.pop()
    else:
        p.append(idx)
        dfs(depth+1,ycnt,idx+1)
        p.pop()
    dfs(depth,ycnt,idx+1)
    
A=[input().rstrip() for _ in range(5)]
visit=[[0]*5 for _ in range(5)]
result=0
p=[]
dfs(0,0,0)
print(result )