인프런 커뮤니티 질문&답변
작성한 질문수
섹션7. 단지 번호 붙이기 (DFS)
해결된 질문
작성
·
294
0
안녕하세요, 강사님.
아래 제 풀이는 in3.txt에 대한 올바른 답을 반환하지 못합니다.
그 이유에 대해서 알 수 있을까요?
즉 강사님의 코드와 제 코드의 차이점에 대해 좀 더 자세히 알 수 있을까요?
<강사님 코드>
import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
def DFS(x, y):
global cnt
cnt+=1
board[x][y]=0
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
DFS(xx, yy)
if name=="__main__":
n=int(input())
board=[list(map(int, input())) for _ in range(n)]
res=[]
for i in range(n):
for j in range(n):
if board[i][j]==1:
cnt=0
DFS(i, j)
res.append(cnt)
print(len(res))
res.sort()
for x in res:
print(x)
<제 코드>
import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 1, 0, 0]
dy=[0, 0, -1, 1]
# '1'인 지점으로부터 그 주위 '1'인 애들 탐색
def DFS(x,y):
global cnt
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
board[xx][yy]=0
cnt+=1
DFS(xx,yy)
if name=="__main__":
n=int(input())
board=[list(map(int, input())) for _ in range(n)]
res=[]
# 먼저 '1'인 지점을 출발점으로 삼고 DFS 호출하기
for i in range(n):
for j in range(n):
if board[i][j]==1:
cnt=0
DFS(i,j)
res.append(cnt)
res.sort()
print(len(res))
for x in res:
print(x)
답변 2
1
안녕하세요^^
import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 1, 0, 0]
dy=[0, 0, -1, 1]
# '1'인 지점으로부터 그 주위 '1'인 애들 탐색
def DFS(x,y):
global cnt
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
board[xx][yy]=0
cnt+=1
DFS(xx,yy)
if name=="__main__":
n=int(input())
board=[list(map(int, input())) for _ in range(n)]
res=[]
# 먼저 '1'인 지점을 출발점으로 삼고 DFS 호출하기
for i in range(n):
for j in range(n):
if board[i][j]==1:
cnt=0
DFS(i,j)
res.append(cnt)
res.sort()
print(len(res))
for x in res:
print(x)위 코드는 첫 줄발하는 격자를 카운트하지 않습니다.
for i in range(n):
for j in range(n):
if board[i][j]==1:
board[i][j] = 0
cnt=1
DFS(i,j)
res.append(cnt)위와 같이 바꿔주면 됩니다.
0
네, 제 코드는 아래와 같습니다.