수학과의 개발자 도전기

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

스스로 푼 문제이고, Silver Level 1 문제이다

W인 지역의 원소 갯수를 구한다음 그것의 제곱값을 answer 딕셔너리의 "W" key의 값에 누적한다

B인 지역도 마찬가지로 진행하면 된다 

- 정답 풀이 : 

from collections import deque

n,m = map(int,input().split())
data=[list(input()) for _ in range(m)]
visit = [[0] * n for _ in range(m)]
answer = {"W" : 0 , "B" : 0}

#방문하지 않은 흰색일 때 진행
#방문하지 않은 파란색일 때 진행 
def bfs(x,y,letter):
    queue=deque()
    queue.append((x,y))
    visit[x][y] = 1
    count = 1
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if not visit[nx][ny] and data[nx][ny] == letter :
                    count += 1
                    visit[nx][ny] = 1
                    queue.append((nx,ny))
    answer[letter] += count*count  
    
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for i in range(m):
    for j in range(n):
        if not visit[i][j]:
            bfs(i,j,data[i][j])
            
print(answer["W"],answer["B"])

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

스스로 푼 문제이고, Silver Level 2 문제이다

dfs로 풀려다가 시간초과, 메모리 초과가 나서 bfs로 풀었다 

data[b].append(a) 때문에 계속 출력 초과가 나다가 없애니까 바로 정답으로 떴다 

문제에서 단방향 도로라는 것에서 힌트를 얻을 수 있다 

- 정답 풀이 : 

from collections import deque

n,m,k,x = map(int,input().split())
data = [[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int,input().split())
    data[a].append(b)
    
visit = [0]*(n+1)
distance = [0]*(n+1)

def bfs(v):    
    queue = deque()
    queue.append(v)
    result = []
    while queue:
        x = queue.popleft()
        if distance[x] == k :
            result.append(x)
        elif distance[x] < k:
            for i in data[x]:
                if not visit[i]:
                    visit[i] = 1
                    distance[i] = distance[x] + 1
                    queue.append(i)
    return result               
                
visit[x] = 1
result = bfs(x)
if len(result) == 0 :
    print(-1)
else:
    result.sort()
    for i in range(len(result)):
        print(result[i])

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

Gold Level2 문제

쉽다고 생각한 문제였다. 1인 지점을 기준으로 주변의 0의 갯수를 세는 bfs를 실행한 다음 그 갯수를 그 위치값에 넣는 식으로 진행했다 

그랬더니 계속 시간초과 문제가 나서 이전 풀이를 다시 보았다 

위 방법으로 진행하면 시간초과가 나므로 관점을 바꿔서 0을 정점으로 보고 연결요소들의 크기를 계산하는 것이다.

각 연결요소를 구할 때 인접한 벽들을 기억하고 있다가 연결요소를 모두 구했을 때 그 크기를 기억해둔 벽들의 좌표에 더해주는 방식으로 진행해 주면 된다 

참고한 블로그

다른 부분은 다 이해가는데, 유독 itr인 부분이 이해가지 않는다 

해당 bfs에 있지만, 아직 방문하지 않은 노드에 대해서 0이면 탐색 진행하고, 1이면 temp에 삽입한다 

bfs를 실행한 뒤 iter += 1을 하는 것으로 보아 0의 갯수를 세는 것 같다 

하나의 0이 영향을 미칠 수 있는 1의 갯수는 여러개이므로 visit 값이 0,1이 아닌 itr로 이루어진건가??

그래야지 각 bfs를 거치면서 0을 중복으로 셀 수 있으니까

- 정답 풀이 :

from collections import deque

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

def bfs(x,y,itr):    
    visit[x][y] = itr
    queue=deque()
    queue.append((x,y))
    count = 1
    temp = []
    while queue: 
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] != itr:
                #0인 경우
                if not data[nx][ny] :  
                    visit[nx][ny] = itr
                    #0의 갯수 세기
                    count += 1
                    queue.append((nx,ny))
                #1인 경우
                else: 
                    temp.append([nx,ny])
                    visit[nx][ny] = itr
    for i,j in temp:
        answer[i][j] += count
        
for i in range(n):
    for j in range(m):
        if data[i][j]:
            answer[i][j] = 1
itr = 1            
for i in range(n):
    for j in range(m):
        #방문하지 않았고, 0인 위치에 대해서 bfs 진행
        if not data[i][j] and not visit[i][j]:
            bfs(i,j,itr)
            itr += 1
            
for i in range(n):
    for j in range(m):
        print(answer[i][j] % 10, end='')
    print()

- 시도해본 풀이 

import sys
from collections import deque
input = sys.stdin.readline

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

def bfs(x,y,data):
    visit = [[0]*m for _ in range(n)]
    visit[x][y] = 1
    queue=deque()
    queue.append((x,y))
    count = 1
    while queue: 
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if data[nx][ny] == '0' and not visit[nx][ny]:
                    visit[nx][ny] = 1
                    count += 1
                    queue.append((nx,ny))
    return str(count)

answer = 0 
for i in range(n):
    for j in range(m):
        if data[i][j] == '1':
            answer = bfs(i,j,data)
            data[i][j] = answer

for i in range(n):
    temp=''
    for j in range(m):
        temp += data[i][j]
    print(temp)

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

두번째 풀이이고, 여전히 풀지 못했다ㅎ

따로 행렬을 만들어서 로봇의 움직임을 확인해야하나 싶었는데, 굳이 그렇게까지는 할 필요 없었고 로봇의 위치를 좌표로 일차 리스트인 visit에 삽입해가면서 방문 여부를 확인하면 된다 

움직임은 동,서,남,북이니까 좌표로 진행하면 된다 

한번의 움직임을 dfs로 진행하는데, 그때의 확률은 count에 누적하고, 성공할 때마다의 확률을 answer에 누적해간다 

dfs 풀 때마다 항상 난관에 부딪히는게 하나의 깊이의 정보를 담는 리스트를 어떻게 처리할 것인가였다 

recursion이 돌면 한번에 여러 깊이가 도는데, 그때의 정보를 어떻게 담아야하는지 몰랐다. 그래서 global도 써보고 했는데

몇 번의 풀이에서 dfs를 진행하고 사용한 리스트를 원상복귀하면 된다 

그게 다음 코드이다

if (nx,ny) not in visit:
            visit.append((nx,ny))
            dfs(nx,ny,count*probability[i],visit)
            visit.pop()

- 정답 풀이 :

import sys
input = sys.stdin.readline

n,E,W,S,N = map(int,input().split())
direction = [(0,1),(0,-1),(1,0),(-1,0)]
probability = [E,W,S,N]

def dfs(x,y,count,visit):
    global answer
    if len(visit) == n+1:
        answer += count
        return 
    for i in range(4):
        nx,ny=x+direction[i][0],y+direction[i][1]
        if (nx,ny) not in visit:
            visit.append((nx,ny))
            dfs(nx,ny,count*probability[i],visit)
            visit.pop()
            
answer=0            
dfs(0,0,1,[(0,0)])            
print(answer*(0.01**n))